请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
import re class Solution(object): def isNumber(self, s): """ :type s: str :rtype: bool """ matchObj=re.match('^\s*[+-]{0,1}((\d)+((\.)(\d)+){0,1}|((\.)(\d)+)|((\d)+(\.)))([eE][+-]{0,1}[\d]+){0,1}\s*$',s) if matchObj: print ("match --> matchObj.group() : ", matchObj.group()) return True else: print ("No match!!") return False给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
第1种最耗时，思路： 拿数组里的第一个数字和后面的数字分别相加，看是否等于target；如果不等于target，那么就继续拿数组里的第二个数字和后面的数字相加；不停的去一个个试...直到等于target，返回这2个数字所在的下标 前置知识： nums = [11, 2，15，7]，里面的数字对应的下标分别是0,1,2,3 for循环嵌套执行顺序：如果一个for循环里还有一个for循环，如果条件不满足，那么里面的for循环会先执行完，外面的for循环才会执行 class Solution: def twoSum(self,nums,target): n = len(nums) # 获取nums的长度，是4 for x in range(n): # 外层循环先取出下标0，对应着数组里的第一个数字 for y in range(x+1,n): # 内层循环取出下标1，对应着数组里的第二个数字 if nums[x] + nums[y] == target: # 如果第一个数字+第二个数字=target return x,y # 上面的判断是对的话，那么就返回下标 break # 并停止程序 else: # 如果上面的条件不满足的话，内层for循环就会继续取出下标2进行判断...如果都不满足，那么外层for循环就会取出下标1...依次类推 continue 第2种，用1个for循环 直接用target 减去 取出的数字，看结果有没有在数组里 class Solution: def twoSum(self,nums,target): n = len(nums) for x in range(n): a = target - nums[x] if a in nums: # 判断a有没有在nums数组里 y = nums.index(a) # 有的话，那么用index获取到该数字的下标 if x == y: continue # 同样的数字不能重复用，所以这里如果是一样的数字，那么就不满足条件，跳过 else: # 否则就返回结果 return x,y break else: continue # 上面的条件都不满足就跳过，进行下一次循环 第3种，用字典提高速度 这个是看了别人的图解答案才知道的（https://leetcode-cn.com/problems/two-sum/solution/tu-jie-ha-xi-biao-by-ml-zimingmeng/），把原先的数组转化成字典，通过字典去查询速度就会快很多。下面的代码我变更了顺序，好理解多了，速度也快了一些。 class Solution: def twoSum(self,nums,target): d = {} n = len(nums) for x in range(n): d[nums[x]] = x # 把数组里的数字作为key，下标作为value存到d字典中 if target - nums[x] in d: # 看另外一个数字有没有在字典里 return d[target-nums[x]],x # 有的话直接就可以返回value了;没有的话会继续循环 经群友指出，上面的写法是错误的。如果先把数组转化成字典的话，target-nums[x]的值很有可能会等于nums[x]，正确的如下： class Solution: def twoSum(self,nums,target): d = {} n = len(nums) for x in range(n): if target - nums[x] in d: return d[target-nums[x]],x else: d[nums[x]] = x给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
BFS实现 class Solution(object): def levelOrderBottom(self, root): if not root: return [] # 创建一个队列，将根节点放入其中 queue = [root] # 用来存放最终结果 res = [] while queue: # 每次遍历的数量为队列的长度 size = len(queue) tmp = [] # 将这一层的元素全部取出，放入到临时数组中，如果节点的左右孩子不为空，继续放入队列 for _ in xrange(size): node = queue.pop(0) tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(tmp) # 翻转最终结果并返回 return res[::-1] BFS实现-2 第一种方式中，我们将最终结果集定义成数组，等所有元素都放置完后，再翻转一下数组。 我们可以将其结构改成链表，以后每层遍历完将结果放入到链表的第一位，这样就自动完成了翻转的功能了 class Solution(object): def levelOrderBottom(self, root): if not root: return [] queue = [root] # 改用双端队列实现，每次都插入到第一位 res = collections.deque() while queue: size = len(queue) tmp = [] for _ in xrange(size): node = queue.pop(0) tmp.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 每次插入到第一位，这样自带了翻转的功能 res.appendleft(tmp) return list(res) DFS实现 class Solution(object): def levelOrderBottom(self, root): if not root: return [] # 用来存放最终结果 res = [] def dfs(root,index): if not root: return # 如果index大于res大小，说明这一层没有对应的集合，需要新创建 if index>len(res): res.append([]) # 将当前层的元素直接放到对应层的末尾即可 res[index-1].append(root.val) # 继续遍历左右节点，同时将层高+1 dfs(root.left,index+1) dfs(root.right,index+1) dfs(root,1) return res[::-1]
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: # 创建一个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 用来最后返回, p 用来遍历 dummy = p = ListNode(None) s = 0 # 初始化进位 s 为 0 while l1 or l2 or s: # 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下面有进位1, 下次加上) s += (l1.val if l1 else 0) + (l2.val if l2 else 0) p.next = ListNode(s % 10) # p.next 指向新链表, 用来创建一个新的链表 p = p.next # p 向后遍历 s //= 10 # 有进位情况则取模, eg. s = 18, 18 // 10 = 1 l1 = l1.next if l1 else None # 如果l1存在, 则向后遍历, 否则为 None l2 = l2.next if l2 else None # 如果l2存在, 则向后遍历, 否则为 None return dummy.next # 返回 dummy 的下一个节点, 因为 dummy 指向的是空的头结点, 下一个节点才是新建链表的后序节点
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度
思路： 这道题主要用到思路是：滑动窗口 什么是滑动窗口？ 其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！ 如何移动？ 我们只要把队列的左边的元素移出就行了，直到满足题目要求！ 一直维持这样的队列，找出队列出现最长的长度时候，求出解！ 时间复杂度：O(n)O(n) class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 while s[i] in lookup: lookup.remove(s[left]) left += 1 cur_len -= 1 if cur_len > max_len:max_len = cur_len lookup.add(s[i]) return max_len给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。 你可以按任意顺序返回答案。
先利用哈希表，再对字典排序。 class Solution: def topKFrequent(self, nums, k): Hash = {} for i in nums: Hash[i] = Hash.get(i, 0) + 1 keyvalues = sorted(Hash.items(), key = lambda x: (x[1], x[0]), reverse=True) return [keyvalues[j][0] for j in range(k)]给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
回溯算法 剪枝 class Solution: def combine(self, n, k): all_combination=[] def backtracking(remain_selection,unfinished_count,prefix): if unfinished_count==0: all_combination.append(prefix[:]) tmp_length=len(remain_selection) for i in range(tmp_length): #此处代码优化可以显著提高运行的效率 if unfinished_count<=tmp_length-i+1: backtracking(remain_selection[i+1:],unfinished_count-1,prefix+[remain_selection[i]]) else: break if n<k or n<=0 or k<=0: return [] backtracking([i for i in range(1,n+1)],k,[]) return all_combination给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。 解集不能包含重复的组合。
回溯算法 from typing import List class Solution: def combinationSum(self, candidates, target): def dfs(candidates, begin, size, path, res, target): if target < 0: return if target == 0: res.append(path) return for index in range(begin, size): dfs(candidates, index, size, path + [candidates[index]], res, target - candidates[index]) size = len(candidates) if size == 0: return [] path = [] res = [] dfs(candidates, 0, size, path, res, target) return res 剪枝提速 from typing import List class Solution: def combinationSum(self, candidates, target): def dfs(candidates, begin, size, path, res, target): if target == 0: res.append(path) return for index in range(begin, size): residue = target - candidates[index] if residue < 0: break dfs(candidates, index, size, path + [candidates[index]], res, residue) size = len(candidates) if size == 0: return [] candidates.sort() path = [] res = [] dfs(candidates, 0, size, path, res, target) return res给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
解题思路 1.length=m+n 如果是奇数中间值的下标就是 length//2,偶数就是 mid=length/2, 也就是mid-1和mid的下标所对应的值/2 2.i,j 分别对应两个数组对应的下标，将小的值插入到new_Arry 3.当new_Arry的长度等于mid的时候就停止循环。 class Solution(object): def findMedianSortedArrays(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: float """ res = 0.0 new_array = [] m = len(nums1) n = len(nums2) length = m + n mid = 0 if length & 1: mid = int(length//2) else: mid = int(length/2) i,j = 0,0 while len(new_array) -1 < mid: if i < m and j < n : if nums1[i] < nums2[j]: new_array.append(nums1[i]) i+=1 continue if nums1[i] >= nums2[j]: new_array.append(nums2[j]) j+=1 continue if i == m and j < n: while j < n and len(new_array) -1 < mid: new_array.append(nums2[j]) j+=1 if i < m and j == n: while i < m and len(new_array) -1 < mid: new_array.append(nums1[i]) i+=1 if length & 1: res = new_array[mid] else: res = (new_array[mid-1] + new_array[mid])/2.0 return res给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
动态规划 对于一个子串而言，如果它是回文串，并且长度大于 22，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 \textrm{``ababa''}“ababa”，如果我们已经知道 \textrm{``bab''}“bab” 是回文串，那么 \textrm{``ababa''}“ababa” 一定是回文串，这是因为它的首尾两个字母都是 \textrm{``a''}“a”。 class Solution: def longestPalindrome(self, s): n = len(s) dp = [[False] * n for _ in range(n)] ans = "" # 枚举子串的长度 l+1 for l in range(n): # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置 for i in range(n): j = i + l if j >= len(s): break if l == 0: dp[i][j] = True elif l == 1: dp[i][j] = (s[i] == s[j]) else: dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j]) if dp[i][j] and l + 1 > len(ans): ans = s[i:j+1] return ans将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R E T O E S I I G E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
class Solution: def convert(self, s, numRows): if numRows < 2: return s res = ["" for _ in range(numRows)] i, flag = 0, -1 for c in s: res[i] += c if i == 0 or i == numRows - 1: flag = -flag i += flag return "".join(res)给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2**31, 2**31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ if -10 < x < 10: return x str_x = str(x) if str_x[0] != "-": str_x = str_x[::-1] x = int(str_x) else: str_x = str_x[:0:-1] x = int(str_x) x = -x return x if -2147483648 < x < 2147483647 else 0 优化解 我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。 反转整数的方法可以与反转字符串进行类比。 我们想重复 “弹出” x 的最后一位数字，并将它 “推入” 到 res 的后面。最后，res 将与 x 相反。 def reverse_better( self, x: int) -> int: y, res = abs(x), 0 # 则其数值范围为 [−2^31, 2^31 − 1] boundry = (1<<31) -1 if x>0 else 1<<31 while y != 0: res = res*10 +y%10 if res > boundry : return 0 y //=10 return res if x >0 else -res请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2**31, 2**31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2**31 − 1) 或 INT_MIN (−2**31) 。
import re class Solution: def myAtoi(self, str: str) -> int: INT_MAX = 2147483647 INT_MIN = -2147483648 str = str.lstrip() #清除左边多余的空格 num_re = re.compile(r'^[\+\-]?\d+') #设置正则规则 num = num_re.findall(str) #查找匹配的内容 num = int(*num) #由于返回的是个列表，解包并且转换成整数 return max(min(num,INT_MAX),INT_MIN) #返回值 ^：匹配字符串开头 [\+\-]：代表一个+字符或-字符 ?：前面一个字符可有可无 \d：一个数字 +：前面一个字符的一个或多个 \D：一个非数字字符 *：前面一个字符的0个或多个 简洁版本： class Solution: def myAtoi(self, s: str) -> int: return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
class Solution(object): def isPalindrome(self, x): return str(x)==str(x)[::-1]给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *
思路 1.先判断s和p的第一个字符是否匹配 2.处理p[1]为*号的情况：匹配0个或多个字符 3.处理.号的情况：匹配一个字符 class Solution: def isMatch(self, s: str, p: str) -> bool: if not p: return not s # 结束条件 first_match = (len(s) > 0) and p[0] in {s[0], '.'} # 先处理 `*` if len(p) >=2 and p[1] == '*': # 匹配0个 | 多个 return self.isMatch(s, p[2:]) or (first_match and self.isMatch(s[1:], p)) # 处理 `.` ，匹配一个 return first_match and self.isMatch(s[1:], p[1:])给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
双指针 class Solution: def maxArea(self, height: List[int]) -> int: l, r = 0, len(height) - 1 ans = 0 while l < r: area = min(height[l], height[r]) * (r - l) ans = max(ans, area) if height[l] <= height[r]: l += 1 else: r -= 1 return ans罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
贪心算法 class Solution: def intToRoman(self, num): # 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中 # 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想 nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] index = 0 res = '' while index < 13: # 注意：这里是等于号，表示尽量使用大的"面值" while num >= nums[index]: res += romans[index] num -= nums[index] index += 1 return res罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。 X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。 给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
class Solution: def romanToInt(self, s): d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000} return sum(d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s))编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
取一个单词 s，和后面单词比较，看 s 与每个单词相同的最长前缀是多少！遍历所有单词。 class Solution: def longestCommonPrefix(self, s): if not s: return "" res = s[0] i = 1 while i < len(s): while s[i].find(res) != 0: res = res[0:len(res)-1] i += 1 return res给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
排序+双指针 解题思路： 暴力法搜索为 O(N^3) 时间复杂度，可通过双指针动态消去无效解来优化效率。 双指针法铺垫： 先将给定 nums 排序，复杂度为 O(NlogN)O(NlogN)。 双指针法思路： 固定 33 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合： 1.当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 33 个数字都大于 00 ，在此固定指针 k 之后不可能再找到结果了。 2.当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。 3.i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动： 当s < 0时，i += 1并跳过所有重复的nums[i]； 当s > 0时，j -= 1并跳过所有重复的nums[j]； 当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和 nums[j]，防止记录到重复组合。 class Solution: def threeSum(self, nums: [int]) -> [[int]]: nums.sort() res, k = [], 0 for k in range(len(nums) - 2): if nums[k] > 0: break # 1. because of j > i > k. if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`. i, j = k + 1, len(nums) - 1 while i < j: # 3. double pointer s = nums[k] + nums[i] + nums[j] if s < 0: i += 1 while i < j and nums[i] == nums[i - 1]: i += 1 elif s > 0: j -= 1 while i < j and nums[j] == nums[j + 1]: j -= 1 else: res.append([nums[k], nums[i], nums[j]]) i += 1 j -= 1 while i < j and nums[i] == nums[i - 1]: i += 1 while i < j and nums[j] == nums[j + 1]: j -= 1 return res给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。
思路: “中序遍历” 思路一：递归 思路二：迭代 代码: 思路一： class Solution: def convertBST(self, root: TreeNode) -> TreeNode: cur = 0 def dfs(root): nonlocal cur if not root: return dfs(root.right) cur += root.val root.val = cur dfs(root.left) dfs(root) return root 思路二： class Solution: def convertBST(self, root: TreeNode) -> TreeNode: cur, stack, p = 0, [], root while p or stack: while p: stack.append(p) p = p.right p = stack.pop() cur += p.val p.val = cur p = p.left return root
