解题过程中二叉树有两种主要的形式：满二叉树和完全二叉树。
1~ 2^(h-1) 个节点（等比数列）。二叉树主要有两种遍历方式：
这两种遍历是图论中最基本的两种遍历方式。
从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式：
前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的，而广度优先遍历的实现一般使用队列来实现。
在现场面试的时候 面试官可能要求手写代码，所以数据结构的定义以及简单逻辑的代码一定要锻炼白纸写出来。因为我们在刷leetcode的时候，节点的定义默认都定义好了，真到面试的时候，需要自己写节点定义的时候，有时候会一脸懵逼！
链式存储的二叉树节点的定义方式：
class TreeNode:
def __init__(self, val, left=None, right=None);
self.val = val
self.left = left
self.right = right
二叉树的定义和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。
递归算法的三个要素：
二叉树前序遍历（递归）：（代码随想录的代码有问题，少了dfs的调用）
用res + dfs函数
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
运用python特性，直接返回递归的函数
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right)
网上基本都是这个精简的代码版本，其实不建议大家照着这个来写，代码确实精简，但隐藏了一些内容，连遍历的顺序都看不出来，所以初学者建议学习版本一的代码，稳稳的打基础。积累自己的代码模板。
二叉树的中序遍历：
用res + dfs函数
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
二叉树的后序遍历：
运用python特性，直接返回递归的函数
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val]
二叉树的前序遍历：
前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。
为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return res
二叉树的中序遍历：
再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。
因为：前序遍历要访问的元素和要处理的元素顺序是一致的，都是中间节点。中序遍历处理顺序和访问顺序是不一致的。
在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack = []
res = []
cur = root
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right # 不需要if cur.right: stack.append(cur.right)
return res
注意：
添加已进栈元素右孩子的时候，不需要if cur.right: stack.append(cur.right)，只需要cur = cur.right，因为已经用了指针cur来让元素进栈。
二叉树的后序遍历：
先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了。
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
if node.left: stack.append(node.left)
if node.right: stack.append(node.right)
return res[::-1]
好复杂，递归掌握了两种，迭代掌握一种就行了。统一风格的之后有空再刷。
层序遍历一个二叉树，需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。
参考hot100的解法，有两种：
普通list和collections.deque
为什么我这样写是不对的：
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue, res = collections.deque([root]), []
while queue:
for i in range(len(queue)):
node = queue.popleft()
if i == len(queue)-1: res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
因为没有把len(queue)记录下来，queue.popleft()之后，len(queue)的长度就变了。
要把len(queue)记录下来，让i==len(queue)-2也是不对的。
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue, res = collections.deque([root]), []
while queue:
length = len(queue)
for i in range(length):
node = queue.popleft()
if i == length-1: res.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
return res
打印之后发现N叉树的node.children是一个list，那就可以用下标来调用。
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if not root:
return []
queue, res = collections.deque([root]), []
while queue:
level, length = [], len(queue)
for _ in range(length):
node = queue.popleft()
level.append(node.val)
for i in range(len(node.children)):
if node.children[i]: queue.append(node.children[i])
# 是不是不需要if node.children[i]
res.append(level)
return res
本题依然是层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了。
if prev:
prev.next = node
prev = node
和
if prev:
prev.next = node
else:
prev = node
有什么区别呢？为什么会结果不一样？
——很精彩，直接prev=node的作用就相当于让prev = prev.next，起到了指针向右移动的作用。
解法1. 用Python特性直接return+递归
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
解法2. 用层序遍历代码模板改一改，记录下遍历的层数就可以了。
解法1. 用层序遍历代码模板改一改
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue, level = collections.deque([root]), 0
while queue:
length = len(queue)
level += 1
for _ in range(length):
node = queue.popleft()
print(node.val)
if not node.left and not node.right:
return level
if node.left: queue.append(node.left) # 为什么不能用elif？
if node.right: queue.append(node.right)
： 如果是用 if 的话，他会一直遍历完所有的if，不管你想判断的条件有没有遍历到，他都会继续执行完所有的if；
而 elif 呢，则会比较快捷，主要还是看你的用处，如果你是想遍历到你的判断条件就不再执行其他判断条件分支语句，那么就用elif；elif 就是当走到符合查询条件的语句后，后面所有的elif和else就不会再被执行；
解法2. 递归法+深度优先搜索
解题思路：
节点不存在时，返回0
左右子节点均不存在时，说明该节点为叶子节点，返回1
左右子节点存在一个时，返回1+minDepth(子节点)
左右子节点均存在时，返回1+较小的minDepth(子节点)
作者：
我按上面思路字面意思写的代码：（AC）
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
if not root.left: return self.minDepth(root.right)+1
if not root.right: return self.minDepth(root.left)+1
if root.left and root.right: return 1+min(self.minDepth(root.right), self.minDepth(root.left))
Nanan的代码：（更简洁）
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
l = self.minDepth(root.left)
r = self.minDepth(root.right)
if root.left and root.right: return 1 + min(l, r)
else: return 1 + l + r
按普通二叉树来解
可以有递归+深度遍历和层次遍历两种解法。
先写递归+深度遍历的写法。
class Solution:
def __init__(self):
self.count = 0
def countNodes(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return
self.count += 1
dfs(node.left)
dfs(node.right)
dfs(root)
return self.count
利用完全二叉树的性质
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
这里关键在于如何去判断一个左子树或者右子树是不是满二叉树呢？
在完全二叉树中，如果递归向左遍历的深度等于递归向右遍历的深度，那说明就是满二叉树。
代码思路：
递归三部曲
1）确定递归参数和返回值：参数是树的根节点，返回值是满二叉树节点数量计算公式
2）确定终止条件：找到满二叉树
3）确定单层递归逻辑：后序遍历
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
level = 1
left, right = root.left, root.right
while left and right:
level += 1
left = left.left
right = right.right
if not left and not root:
return 2**level - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
这种解法好好消化一下。
咋眼一看这道题目和104.二叉树的最大深度很像，其实有很大区别。
求深度可以从上到下去查，所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）。
为什么104.二叉树的最大深度中求的是二叉树的最大深度，也用的是后序遍历？
那是因为代码的逻辑其实是求的根节点的高度，而根节点的高度就是这棵树的最大深度，所以才可以使用后序遍历。
递归三部曲：
一开始根据上面的思路写出来的代码：
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def getHight(node):
if not node:
return 0
if abs(getHight(node.left)-getHight(node.right)) > 1: return -1
else: return max(getHight(node.left), getHight(node.right)) + 1
result = getHight(root)
if result == -1:
return False
else:
return True
只通过了一部分测试用例，就像上面的测试用例通不过。
检查发现递归的代码里面没有检查左右子树，只比较了左右子树的高度。
添加两行代码：
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def getHight(node):
if not node:
return 0
### 添加的代码 ###
if getHight(node.left) == -1: return -1
if getHight(node.right) == -1: return -1
################
if abs(getHight(node.left)-getHight(node.right)) > 1: return -1
else: return max(getHight(node.left), getHight(node.right)) + 1
result = getHight(root)
if result == -1:
return False
else:
return True
结果呢，超出了时间…
——把getHight(node.left)和getHight(node.right)分别用leftHeight和rightHeight保存下来，也就是说只调用一次：
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def getHight(node):
if not node:
return 0
leftHeight, rightHeight = getHight(node.left), getHight(node.right)
if leftHeight == -1: return -1
if rightHeight == -1: return -1
if abs(leftHeight-rightHeight) > 1: return -1
else: return max(leftHeight, rightHeight) + 1
if getHight(root) == -1:
return False
else:
return True
AC!
这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。
先使用递归的方式，来做前序遍历。要知道递归和回溯就是一家的，本题也需要回溯。
递归三部曲
not root的话会很麻烦，因为本题要找到叶子节点，就开始结束的处理逻辑了（把路径放进result里）。cur不为空，其左右孩子都为空的时候，就找到叶子节点。if not root.left and not root.right:
终止处理逻辑（注意要转化成字符串表示路径）
path.append(cur.val)return。if cur.left: traversal(cur.left, path, result)
if cur.right: traversal(cur.right, path, result)
if cur.left:
traversal(cur.left, path, result)
path.pop()
if cur.right:
traversal(cur.right, path, result)
path.pop()
按上面的分析写出来我理解的代码：
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traverse(cur, path, result):
path.append(cur.val)
if not cur.left and not cur.right: #说明到达叶子结点了
result.append("->".join(map(str, path)))
#不用map的话，path里面是int，不可以用join
return
if cur.left:
traverse(cur.left, path, result)
path.pop()
if cur.right:
traverse(cur.right, path, result)
path.pop()
path = []
result = []
if not root: return result
traverse(root, path, result)
return result
if not root: return既可以写在外函数binaryTreePaths里面，也可以写在traverse函数里面。写在binaryTreePaths是if not root: return result.
精简版的代码理解一下：
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
def traverse(cur, path, result):
path.append(cur.val)
if not cur.left and not cur.right: #说明到达叶子结点了
result.append("->".join(map(str, path)))
#不用map的话，path里面是int，不可以用join
return
if cur.left:
traverse(cur.left, path[:], result)
# path.pop()
if cur.right:
traverse(cur.right, path[:], result)
# path.pop()
path = []
result = []
if not root: return result
traverse(root, path, result)
return result
变化：去掉path.pop()，traverse里面的path改成path[:]。
为什么可以这样？——好饿，第一遍先不想了。
有了思路，自己试一下：
class Solution:
result = 0
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return
if node.left:
dfs(node.left)
if not node.left.left and not node.left.right:
self.result += 1
if node.right: dfs(node.right)
return self.result
运行出来的结果是错的。
和代码随想录视频讲的一对比，我的递归只是递归遍历，具体算result甚至有点像层序遍历，而人家的递归是后序遍历把左子树和右子树的结果加在一起，说白了就是更整体。
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
leftNum = self.sumOfLeftLeaves(root.left)
if root.left and not root.left.left and not root.left.right:
leftNum = root.left.val
rightNum = self.sumOfLeftLeaves(root.right)
return leftNum + rightNum
按回溯法的思路写下来我的思路：
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def backtracking(node, path):
if not node:
if sum(path) == targetSum:
return True
return False
path.append(node.val)
if node.left: backtracking(node.left, path)
if node.right: backtracking(node.right, path)
path.pop()
path = []
return backtracking(root, path)
运行结果：都是错的…
【题解】
能掌握递归方式就够了。
没有中结点的处理逻辑，那么就前中后序都可以。
为什么需要判断 node.left 和 node.right 是否同时存在，而不是判断 node 是否存在？
——因为只有左右孩子都不存在，才是叶子结点。
判断最大的根结点 root 是否存在还是需要做的，可以在外函数hasPathSum里面做。
知道了这两点，修改代码为：
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def backtracking(node, path):
if not node.left and not node.right:
if sum(path) == targetSum:
return True
return False
path.append(node.val)
if node.left: backtracking(node.left, path)
if node.right: backtracking(node.right, path)
path.pop()
path = []
if not root:
return False
return backtracking(root, path)
运行结果：除了空结点，其他case都错误。
if backtracking(node.left, path)是否为True的，否则整体运行结果的返回值是nullprint("sum(path)", sum(path))，发现path里面没有加node.left和node.right就直接return了，每次计算只到叶子结点上面一层，所以计算的值永远都不对。if node.left和if node.right之后将node.left和node.right加入path，最大的根结点root.val什么时候加入path呢？在外函数hasPathSum里面吗？修改代码为：
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def backtracking(node, path):
if not node.left and not node.right:
print("sum(path)", sum(path))
if sum(path) == targetSum:
return True
return False
if node.left:
path.append(node.left.val)
if backtracking(node.left, path):
return True
path.pop()
if node.right:
path.append(node.right.val)
if backtracking(node.right, path):
# 不能直接改成return backtracking(node.right, path)
# 可能因为二叉树也可能没有右或者左叶子结点？
return True
path.pop()
return False # case2满足这一情况
if not root:
return False
path = [root.val]
return backtracking(root, path)
AC!
代码随想录的题解是用count递减代替了sum(path). 可以作为一种参考。
class Solution:
def traversal(self, cur: TreeNode, count: int) -> bool:
# 终止条件
if not cur.left and not cur.right and count == 0: # 遇到叶子节点，并且计数为0
return True
if not cur.left and not cur.right: # 遇到叶子节点直接返回
return False
# 单层处理的逻辑
if cur.left: # 左
count -= cur.left.val
if self.traversal(cur.left, count): # 递归，处理节点
return True
count += cur.left.val # 回溯，撤销处理结果
if cur.right: # 右
count -= cur.right.val
if self.traversal(cur.right, count): # 递归，处理节点
return True
count += cur.right.val # 回溯，撤销处理结果
return False
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return False
return self.traversal(root, sum - root.val) # 已经减去root.val
精简版代码：（留给二刷写）（代码随想录的视频有讲如何精简）
在这里插入代码片
【看了视频的理解】：
如何做到只要找到一条路径就返回，不继续遍历剩余结点的？靠的就是return True. 并且找到一条路径之后，要把Ture一级一级return上去。
💡递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：
如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
按照上题的理解写了我的代码：
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def backtracking(node, path, result):
# 终止条件
if not node.left and not node.right:
print("path:", path)
if sum(path) == targetSum:
result.append(path)
print("result:", result)
return result
# 单层递归逻辑
if node.left:
path.append(node.left.val)
backtracking(node.left, path, result)
path.pop()
if node.right:
path.append(node.right.val)
backtracking(node.right, path, result)
path.pop()
if not root:
return []
path, result = [root.val], []
backtracking(root, path, result)
return result
运行结果：result里面只有[[5], [5]]
因为
result.append(path[:])而不是result.append(path)。
看一下我去年写的方法：
更简洁一点，而且就是用的我之前想的判断root在不在，而不是左右孩子都要判断一下在不在。
应该就是leetcode的题解，二刷的时候看一下。
class Solution:
def pathSum(self, root: TreeNode, targetSum: int) -> List[List[int]]:
ret = list()
path = list()
def dfs(root: TreeNode, targetSum: int):
if not root:
return
path.append(root.val)
targetSum -= root.val
if not root.left and not root.right and targetSum == 0:
ret.append(path[:])
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop()
dfs(root, targetSum)
return ret
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 第一步
if not postorder:
return []
# 第二步、第三步
node, index = TreeNode(postorder[-1]), 0
for i in range(len(inorder)):
if inorder[i] == node.val:
index = i
break # 我让i遍历，然后index=i说是局部变量——>要先把index初始化一下
# 第四步、第五步
inorderleft, inorderright = inorder[:index], inorder[index+1:]
postorderleft, postorderright = postorder[:index], postorder[index:]
# 第六步
if inorderleft: node.left = self.buildTree(inorderleft, postorderleft)
if inorderright: node.right = self.buildTree(inorderright, postorderright)
return node
运行结果：
inorderleft: [9]
inorderright: [15, 20, 7]
postderleft: [9]
postorderright: [15, 7, 20, 3]
inorderleft: []
inorderright: []
postderleft: []
postorderright: [9]
inorderleft: [15, 20]
inorderright: []
postderleft: [15, 7]
postorderright: [20, 3]
inorderleft: [15]
inorderright: []
postderleft: [15]
postorderright: [7]
inorderleft: []
inorderright: []
postderleft: []
postorderright: [15]
发现每一步多打了很多空[]，而且20消失了。
经验：
idx = inorder.index(postorder[-1])postorderleft, postorderright = postorder[:idx], postorder[idx:-1]class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
# 第一步 —— 终止条件
if not postorder:
return
# 第二步、第三步
node = TreeNode(postorder[-1])
idx = inorder.index(postorder[-1])
# 第四步、第五步
inorderleft, inorderright = inorder[:idx], inorder[idx+1:]
# print("inorderleft:", inorderleft), print("inorderright:", inorderright)
postorderleft, postorderright = postorder[:idx], postorder[idx:-1]
# print("postderleft:", postorderleft), print("postorderright:", postorderright)
# 第六步
node.left = self.buildTree(inorderleft, postorderleft)
node.right = self.buildTree(inorderright, postorderright)
return node
AC!
去年看labuladong的代码，跟上面这版基本一样，更简洁一点：
(但是隐藏了一些细节，还是写明白，自己不容易搞糊涂)
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
if not inorder or not postorder:
return
root = TreeNode(postorder[-1])
idx = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:idx], postorder[:idx])
root.right = self.buildTree(inorder[idx+1:], postorder[idx:-1])
return root
【题解思路】：
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
三部曲
为什么106. 从中序与后序遍历序列构造二叉树就需要判断？
——因为106判断的不是整个数组，而是postorder or inorder。这个是可以当作递归的终止条件的。
用python的max(nums)的话，可以直接判断nums是否为0。
如果不用max(nums)，而是像C++代码示例一样，遍历去替换maxValue的话，判断到了叶子结点就可以停止。（无非是早停止还是晚停止的问题？）
以上代码比较冗余，效率也不高，但逻辑比较清晰。
class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
# 递归终止条件
if not nums:
return
# 单层递归逻辑
maxValue = max(nums)
maxIndex = nums.index(maxValue)
root = TreeNode(maxValue)
leftnums, rightnums = nums[:maxIndex], nums[maxIndex+1:]
root.left = self.constructMaximumBinaryTree(leftnums)
root.right = self.constructMaximumBinaryTree(rightnums)
return root
改了递归终止条件就AC了。二刷可以看看其他复杂点的代码思路。主要是总结什么时候需要用什么。
看了看去年的解法，6.10的逻辑不清楚，6.8的跟代码随想录第二版有点像。
一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if一下， 终止条件也会相应的调整。
【题解思路】：
t1 和 t2，如果t1 == NULL 了，两个树合并就应该是 t2 了（如果t2也为NULL也无所谓，合并之后就是NULL）。t2 == NULL，那么两个数合并就是t1（如果t1也为NULL也无所谓，合并之后就是NULL）。最终t1就是合并之后的根节点。
按上面的思路写出来代码：
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
# 终止条件
if not root1: return root2
if not root2: return root1
# 单层递归的逻辑
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
直接AC了！
【总结】
虽然中序遍历和后序遍历也可以的，但是前序遍历是最好理解的，我建议大家用前序遍历来做就OK。
如上的方法修改了t1的结构，当然也可以不修改t1和t2的结构，重新定义一个树。
这不是我们第一次操作两棵二叉树了，在二叉树：我对称么？中也一起操作了两棵二叉树。
本题考查的就是二叉搜索树的遍历方式。二叉搜索树，递归遍历和迭代遍历和普通二叉树都不一样。因为二叉搜索树的有序性，遍历的时候要比普通二叉树简单很多。针对二叉搜索树的题目，一样要利用其特性。
【递归】
root.val > val，搜索左子树，如果root.val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。根据上面的三部曲写出自己理解的代码：
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val > val:
self.searchBST(root.right, val)
elif root.val < val:
self.searchBST(root.left, val)
返回的结果全是空值。
原因：
每一步self.searchBST没有向上返回吗？
很多录友写递归函数的时候 习惯直接写 searchBST(root->left, val)，却忘了 递归函数还有返回值。
递归函数的返回值是什么? 是 左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。
所以要 result = searchBST(root->left, val)。
按上面修改了：
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val > val:
return self.searchBST(root.right, val)
elif root.val < val:
return self.searchBST(root.left, val)
结果还是全空值。
原因：if条件判断之后的语句，搜索方向写反了。
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root or root.val == val:
return root
if root.val > val:
return self.searchBST(root.left, val)
elif root.val < val:
return self.searchBST(root.right, val)
【迭代】
因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。
对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。
而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。
根据上面的思路写出来：
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val > val:
root = root.left
elif root.val > val:
root = root.right
else:
return root
return []
结果：
case2返回不了空列表。
发现写错了，一直在判断root.val > val.
改成下面的：
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val > val:
root = root.left
elif root.val < val:
root = root.right
else:
return root
# return None
AC!
return None加或不加都不影响结果：试了下让这个函数直接return，case2也是通过的，因此，应该是leetcode运行的时候有一个初始的空列表。
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
return
甚至18天前还刷过一次，刷完了现在丝毫没有印象，原因：1. 没有巩固 2. 不是理解了套路和整体思路自己写的代码，是单纯看懂了题解写出来的，不够模板化，没有形成自己的东西。
这题不管是递归还是迭代，代码随想录都给出了很多种解法。递归解法有两种：1. 使用一个最小值的方法 2. 使用一个指针pre直接取最小值。迭代解法和之前刷过的题解的迭代解法很像。二刷如果有捋不清这几种解法的地方，再去看一下视频讲解。
【递归思路】
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
可以递归中序遍历将二叉搜索树转变成一个数组，然后只要比较一下，这个数组是否是有序的，注意二叉搜索树中不能有重复元素。这样写是最直观的，但这样不是最优的方法，需要额外定义一个数组。其实不用转变成数组，可以在递归遍历的过程中直接判断是否有序。
确定递归函数，返回值以及参数
确定终止条件
如果是空二叉树，那它既是完全二叉树，也是满二叉树，也是二叉搜索树，也是平衡二叉搜索树，什么二叉树都是。
return True
确定单层递归的逻辑
两种方法：
maxVal >= root.val，就返回false，注意元素相同时候也要返回false。pre指针迭代法：pre指针始终指向当前结点的前一个结点。这里代码随想录视频把为什么pre可以和当前结点root比较说清楚了，如果n刷有不清楚的地方再去看看视频。
按上面的思路写一版代码：
最小值法：
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
maxValue = - 2 ^ 31 - 1 # 注意不是2^^31，只有1个尖号
# 左
left = self.isValidBST(root.left)
# 中
if root.val >= maxValue:
maxValue = root.val
else:
return False
# 右
right = self.isValidBST(root.right)
# print(root.val, left, right) 加一行debug
return left and right
发现返回的全是True，就没有False的时候。
maxValue要定在全局，而不是定义在isValidBST函数里面，不然每次递归maxValue都会被重置。float("-inf")，防止有比- 2 ^ 31 - 1更小的。class Solution:
def __init__(self):
self.maxValue = float("-inf")
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
# 左
left = self.isValidBST(root.left)
# 中
if root.val > self.maxValue:
self.maxValue = root.val
else:
return False
# 右
right = self.isValidBST(root.right)
print(root.val, self.maxValue, left, right)
return left and right
AC!
pre指针迭代法：
class Solution:
def __init__(self):
self.pre = None # pre指针
def isValidBST(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
# 左
left = self.isValidBST(root.left)
# 中
if root.val > pre.val: # 有错误，应该用self
pre = root # 有错误，应该用self
else:
return False
# 右
right = self.isValidBST(root.right)
# print(root.val, self.maxValue, left, right)
return left and right
执行出错。
“# 中”的逻辑也不是这样：
if self.pre and root.val < self.pre.val:
return False
else:
self.pre = root
改成正确的：
# 中
if self.pre and root.val < self.pre.val:
return False
self.pre = root
这样的方法在前面的二叉树题目也遇到过，不明白可以看看这题的代码随想录视频。
【迭代法】
层序遍历用stack。用两个指针cur和pre指向当前结点和上一个结点。
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
stack, cur, pre = [], root, None
while cur or stack:
if cur:
stack.append(cur)
cur = cur.left # 先找到最左边结点
else:
cur = stack.pop()
if pre and pre.val >= cur.val: # 记得有等号
return False
pre = cur
cur = cur.right
return True
二叉搜索树采用中序遍历，其实就是一个有序数组。
在一个有序数组上求两个数最小差值，这是不是就是一道送分题了。
不知怎么想到了这种解法，写一下这道题：
class Solution:
def __init__(self):
self.result = 0
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left = self.getMinimumDifference(root.left)
res = 0
if root.left: res = abs(root.val-root.left.val)
if root.right: res = min(res, abs(root.val-root.right.val))
right = self.getMinimumDifference(root.right)
self.result = min(left, res, right)
结果自然是不对了。
题解，用两个指针直接解这道题，不需要再开辟一个数组了。
递归三部曲：
if root: return 什么也不返回代码随想录里面用了一个嵌套的traversal函数，那么什么时候需要嵌套的函数，什么时候不需要呢？
——与主函数返回值不同，这可能就是最什么需要再定义一个递归函数，而不是直接用主函数递归的原因。
根据上面题解写了一版我自己的理解：
class Solution:
def __init__(self):
self.pre = None
self.result = float("inf")
def traversal(self, root):
if not root:
return
self.traversal(root.left)
if self.pre: self.result = min(self.result, abs(root.val-pre.val))
print(self.result)
pre = root
self.traversal(root.right)
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.traversal(root)
return self.result
结果：
为什么啥返回值都没有呢？——没有把self.pre和self.result调用对。
更改后：
class Solution:
def __init__(self):
self.pre = None
self.result = float("inf")
def traversal(self, root):
if not root:
return
self.traversal(root.left)
if self.pre: self.result = min(self.result, abs(root.val-self.pre.val))
print(self.result)
self.pre = root
self.traversal(root.right)
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.traversal(root)
return self.result
AC!
提到二叉搜索树，遍历顺序一定是中序遍历。
双指针思路：
遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
关键是在有序数组上的话，好搞，在树上怎么搞呢？
这就考察对树的操作了。
在二叉树：搜索树的最小绝对差中我们就使用了pre指针和cur指针的技巧，这次又用上了。
弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。
可以只遍历一遍数组，找出最大频率（maxCount），如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），是不是感觉这里有问题，result怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大频率呢。
所以下面要做如下操作：
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。
先自己试着写一遍这个代码：（这样更能理解遇到的细节小坑如何解决）
class Solution:
def __init__(self):
self.pre = None
self.count = 1
self.maxCount = 1
self.res = []
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root): # root就是cur
if not root:
return
# 左
traversal(root.left)
# 中
if self.pre:
if self.pre.val == root.val:
self.count += 1
if self.count >= self.maxCount:
self.maxCount = self.count
self.res.append(self.pre.val)
else:
self.count = 1
self.res = []
self.pre = root
# 右
traversal(root.right)
traversal(root)
return self.res
结果：
应该把self.count >= self.maxCount分成>和=两种情况分开讨论，Pre和count的更新分开在两段if 判断语句里。
修改如下：
class Solution:
def __init__(self):
self.pre = None
self.count = 1
self.maxCount = 1
self.res = []
def findMode(self, root: Optional[TreeNode]) -> List[int]:
def traversal(root): # root就是cur
if not root:
return
# 左
traversal(root.left)
# 中
if self.pre:
if self.pre.val == root.val:
self.count += 1
else:
self.count = 1
self.pre = root
if self.count == self.maxCount:
self.res.append(self.pre.val)
if self.count > self.maxCount:
self.maxCount = self.count
self.res = [self.pre.val]
# 右
traversal(root.right)
traversal(root)
return self.res
树的遍历不可以从下向上遍历，只能从根作为入口，由上向下进行遍历。但是，处理的顺序可以从下向上进行处理——回溯，将处理结果一层一层返回上去。遍历的顺序就是后序遍历——左右中了。中是处理逻辑，也就是回溯的过程。
两种情况：
p or q就向上返回，如果没有就返回None. 对于中间节点，左右子树都不为空就说明当前的中就是最近公共祖先。代码处理这两种情况的逻辑相同。
试着分析代码逻辑，按递归三部曲来：
p or q。（与主函数lowestCommonAncestor返回值不同，这可能就是最什么需要再定义一个递归函数，而不是直接用主函数递归的原因？）root为空，终止遍历试着写出代码：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
def traversal(root):
if not root:
return
left = traversal(root.left)
right = traversal(root.right)
if left and right:
return root
if left:
return True
if right:
return True
if root.val == p.val or root.val == q.val:
return True
else:
return False
写出一版，挺错的…输出全是False。
看了一遍代码随想录的代码讲解，再写一遍python代码：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return # return和return root结果相同
if root.val == p.val or root.val == q.val:
return root # 这两个条件都是终止条件
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: return root
if left and not right: return left
if right and not left: return right
总结：
lowestCommonAncestor递归返回结果都是一样的，因此不需要再定义一个traversal函数，直接用主函数递归。if not root or root.val == p.val or root.val == q.val:
return root
题解的笔记：
在递归函数有返回值的情况下：如果要搜索一条边，递归函数返回值不为空的时候，立刻返回，如果搜索整个树，直接用一个变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。
这道题目刷过的同学未必真正了解这里面回溯的过程，以及结果是如何一层一层传上去的。
那么我给大家归纳如下三点：
- 求最小公共祖先，需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。
- 在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。
- 要理解如果返回值left为空，right不为空为什么要返回right，为什么可以用返回right传给上一层结果。
可以说这里每一步，都是有难度的，都需要对二叉树，递归和回溯有一定的理解。
【题解】
本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。
在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？
因为是有序树，所以 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。
那么只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是p 和 q的公共祖先。
那问题来了，一定是最近公共祖先吗？
此时节点5是不是最近公共祖先？ 如果 从节点5继续向左遍历，那么将错过成为p的祖先， 如果从节点5继续向右遍历则错过成为q的祖先。
所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。
而递归遍历顺序，本题就不涉及到 前中后序了（这里没有中节点的处理逻辑，遍历顺序无所谓了）。
递归三部曲
在这里调用递归函数的地方，把递归函数的返回值left，直接return。
在二叉树：公共祖先问题中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。
根据上面题解写出我的代码：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
AC!
本题的迭代法写法也很简单：
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val > p.val and root.val > q.val:
root = root.left
if root.val < p.val and root.val < q.val:
root = root.right
else:
return root
这样写有的测试用例通不过。
第二个if改成elif就通过了。
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if root.val > p.val and root.val > q.val:
root = root.left
elif root.val < p.val and root.val < q.val:
root = root.right
else:
return root
为什么呢？
chatgpt的解答：
区别：
条件判断和分支结构：
第一段代码使用了elif，即如果root.val > p.val and root.val > q.val这个条件不满足，才会检查下一个条件root.val < p.val and root.val < q.val。这意味着一旦其中一个条件成立，就不会再检查另一个条件，直接进入else分支。
第二段代码使用了两个的if语句，分别检查root.val > p.val and root.val > q.val和root.val < p.val and root.val < q.val。这样即使第一个if条件成立，代码仍会继续检查第二个if条件。
可能的效果：
逻辑正确性：
第一段代码的逻辑是正确的，因为在一个节点不满足第一个条件时，才有必要检查第二个条件。这确保了在root.val同时大于p.val和q.val或者同时小于p.val和q.val时，树的遍历能在正确的子树继续。
第二段代码可能会引发逻辑错误，因为它会继续检查第二个条件，即使第一个条件已经改变了root节点。例如，如果root.val大于p.val和q.val，在执行了root = root.left之后，代码会继续检查root.val < p.val and root.val < q.val，即使root节点已经发生了变化，这可能导致跳过else部分的执行，进而可能导致在某些情况下返回错误的结果。
性能影响：
第一段代码在逻辑上是分支处理的，直接决定了下一个步骤，所以执行效率更高。
第二段代码由于每个循环都会检查两个条件，即使第一个条件成立后仍然会检查第二个条件，增加了不必要的检查次数，可能导致略微的性能损失。
所以递归法也应该用elif，而不是if.
【题解】
其实可以不考虑题目中提示所说的改变树的结构的插入方式。
只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
其实在二叉搜索树中插入任何一个结点，都可以在叶子结点找到插入位置。
递归三部曲：
这里递归函数要不要有返回值呢？
可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码。
有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。
root.left或者root.right将其接住。定义返回值的写法：
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)
if val < root.val: root.left = self.insertIntoBST(root.left, val)
elif val > root.val: root.right = self.insertIntoBST(root.right, val)
return root
不定义返回值的写法：
找到插入的节点位置，直接让其父节点指向插入节点，结束递归，也是可以的，只是没有加上返回值便利。
在这里插入代码片
迭代法：
在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作。
在二叉树：搜索树的最小绝对差 和二叉树：我的众数是多少？中，都是用了记录pre和cur两个指针的技巧，本题也是一样的。只不过改成用parent和cur记录。
在这里插入代码片
【题解思路】
搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑。
【视频讲解】
确定递归函数参数和返回值
确定递归终止条件
遇到要删除的结点就终止了，也是删除结点的逻辑，这就用到了上面的5种情况。
视频中讲了代码里面return的空返回到哪里去了——上一层递归的时候会让root.left等于下一层递归的返回值。
重点讲一下第5种情况的代码，分2步：
按上面的逻辑写出自己版本的代码：
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root: return # 1. 可能是树为空或者到达了叶子结点，也就是没找到要删除的节点
if root.val == key:
if not root.left and not root.right:
return # 2. 删除叶子结点
if root.left and not root.right:
return root.left # 3. 左不空右为空
if not root.left and root.right:
return root.right # 4. 左为空右不空
if root.left and root.right:
cur = root.right
while cur.left: cur = cur.left
cur.left = root.left
return root.right # 5. 左不空右不空
root.left = self.deleteNode(root.left, key)
root.right = self.deleteNode(root.right, key)
return root
AC!
【解题思路】
递归三部曲：
相当于把节点0的右孩子（节点2）返回给上一层，然后用节点3的左孩子 把下一层返回的 节点0的右孩子（节点2） 接住。此时节点3的左孩子就变成了节点2，将节点0从二叉树中移除了。
按上面的思路写出代码：
class Solution:
def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
if not root: return
if root.val < low: return self.trimBST(root.right, low, high)
if root.val > high: return self.trimBST(root.left, low, high)
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
AC!
刷递归法就行了。
之后刷二叉树的题也是什么方法方便刷什么方法，不需要非得递归/迭代都刷一遍。
【思路】
确定递归函数返回值及其参数
这里定义的是左闭右闭区间，在不断分割的过程中，也会坚持左闭右闭的区间，这又涉及到我们讲过的循环不变量。
怎么看出来是左闭右闭区间的？
——可能因为数组下标都是具体指定好了的。
确定递归终止条件
这里定义的是左闭右闭的区间，所以当区间 left > right 的时候，就是空节点了。
确定单层递归的逻辑
mid = (left + right) / 2这么写其实可能会有一个问题，就是数值越界，例如left和right都是最大int，这么操作就越界了，在二分法中尤其需要注意！（我感觉这样是c++代码需要考虑的？——做二分法的时候看一看）
所以可以这么写：mid = left + ((right - left) / 2)
chatgpt回复：
问题解析
方法 1：mid = (left + right) / 2
这种计算中间点的方式在数学上是正确的，但在计算机中可能导致整数溢出。原因如下：
- 当left和right都是较大的整数时，它们的和left + right可能超出整数类型的最大表示范围，导致溢出。
- 在溢出发生时，left + right的结果可能是负数或者截断成一个错误的正数，这会导致mid的计算结果不正确，进而可能访问数组的非法索引或导致其他不可预期的行为。
例如，在使用32位整数的系统中，如果left和right都接近INT_MAX（21474837），那么left + right可能会超过21474837，引发溢出。方法 2：mid = left + ((right - left) / 2)
这种计算方式则是更安全的，因为它避免了直接将两个大整数相加：
- right - left是两个接近值的差，这个差在数值上总是比它们本身小得多。因此，right - left的计算不太可能导致溢出。
- 在计算(right - left) / 2时，差值已经较小，这个除法不会导致大数问题。
最终，left + (right - left) / 2也不会因为整数溢出而出现问题。
但使用python不会有溢出的问题:
在Python中，整数的处理与许多其他语言不同，因为Python中的整数是任意精度的。这意味着，Python的整数不会像C++或Java中的32位或位整数那样固定大小，因此不会有溢出的问题。Python会动态调整整数的大小以适应需要的范围。
因此mid = (left + right) / 2和mid = left + ((right - left) / 2)在正常使用中不会出现错误。但在跨语言编程或保持代码良好习惯时，推荐使用后者。
mid = left + ((right - left) / 2)的写法相当于是如果数组长度为偶数，中间位置有两个元素，取靠左边的
根据上面的思路写出来一版代码：
由于上面题解的递归函数与主函数参数不同，因此还是要重新定义一个traversal函数。
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def traversal(nums, left, right):
if left > right: return
mid = ( left + right ) // 2
root = TreeNode(nums[mid])
root.left = traversal(nums, left, mid-1)
root.right = traversal(nums, mid+1, right)
return root
return traversal(nums, 0, len(nums)-1)
之前的题解代码：（感觉像二分法）
由于主函数与需要递归的函数参数和返回值都相同，因此不需要额外定义一个递归函数了。
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
if not nums:
return
mid = len(nums) // 2
mid_node = TreeNode(nums[mid])
mid_node.left = self.sortedArrayToBST(nums[:mid])
mid_node.right = self.sortedArrayToBST(nums[mid+1:])
return mid_node
其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。
那么知道如何遍历这个二叉树，也就迎刃而解了，从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
递归法：
本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。
pre指针的使用技巧，我们在二叉树：搜索树的最小绝对差 (opens new window)和二叉树：我的众数是多少？ (opens new window)都提到了，这是常用的操作手段。
按上面的思路自己写了一遍代码：
class Solution:
def __init__(self):
self.pre = 0
self.cur = root.val
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return
self.convertBST(root.right)
self.cur += self.pre
self.pre = self.cur.val # 记得是self.cur.val
self.convertBST(root.left)
发现我不知道怎么用两个指针去遍历二叉搜索树。
看了看题解的写法，就是上面那样写的，自动就向下深度遍历了，同时全局变量cur和pre也会一直跟着变化。
但不同的是，traversal代码什么也不返回，而主函数是要返回累加树的根节点的。因此不能把主函数当作递归函数。
class Solution:
def __init__(self):
self.pre = 0
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def traversal(cur):
if not cur:
return
traversal(cur.right)
cur.val += self.pre
self.pre = cur.val
traversal(cur.left)
traversal(root)
return root
迭代法：
迭代法其实就是中序模板题了，在二叉树：前中后序迭代法 和二叉树：前中后序统一方式迭代法 可以选一种自己习惯的写法。
按中序迭代遍历模板写了一版：
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = []
res = []
cur = root
pre = 0
while cur or stack:
if cur:
stack.append(cur)
cur = cur.right
else:
cur = stack.pop()
pre += cur.val
res.append(pre)
cur = cur.left
return res
结果：
不是要返回这个res集合，而是要把这个二叉树改成累加树，然后返回累加树根节点。
改下代码：
class Solution:
def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = []
res = []
cur = root
pre = 0
while cur or stack:
if cur:
stack.append(cur)
cur = cur.right
else:
cur = stack.pop()
pre += cur.val
cur.val = pre # 修改cur的结点值
cur = cur.left
return root
AC!
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- aiwanbo.com 版权所有 赣ICP备2024042808号-3
违法及侵权请联系：TEL:199 18 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务