106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
手动构造的步骤：
后序确定根，中序分左右(子树)。
以 后序数组的最后一个元素（根）为切割点，先切中序数组，根据中序数组，反过来再切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: def traversal(inorder, postorder): if not postorder: return None # 根 rootValue = postorder[-1] root = TreeNode(rootValue) # 叶子 if len(postorder) == 1: return root #3. 找切割点 inorder_index = inorder.index(rootValue) # 4. 切割 inorder 左、右 leftInorder = inorder[:inorder_index] rightInorder = inorder[inorder_index+1:] # 5. 切割 postoder 左、右 postorder = postorder[:-1] leftPostorder = postorder[:len(leftInorder)] rightPostorder = postorder[len(leftInorder):] # 6. 递归处理 root.left = traversal(leftInorder, leftPostorder) root.right = traversal(rightInorder, rightPostorder) return root if len(inorder) == 0 or len(postorder)==0: return None root = traversal(inorder, postorder) return root
654.最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
- 创建一个根节点，其值为
nums中的最大值。 - 递归地在最大值 左边 的 子数组前缀上 构建左子树。
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树
递归公式：
- 函数参数和返回值
参数：待构建数组nums。
返回值：通过nums构建的树的根节点root - 终止条件
nums为空，无法继续构建。 - 单层逻辑
按照题目的描述。选出最大值，递归左右子树。
class Solution: def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]: def construct(nums): if not nums: return None max_value = max(nums) max_index = nums.index(max_value) root = TreeNode(max_value) left_nums = nums[:max_index] right_nums = nums[max_index+1:] root.left = construct(left_nums) root.right = construct(right_nums) return root return construct(nums)
（可以优化一下参数，每次不用传nums，而是传数组的左右边界）
617.合并二叉树
合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
递归公式：
- 函数参数和返回值
参数：两棵树的节点 t1, t2
返回值：合并后的节点 - 终止条件：
t1,t2其中一个为None，则直接返回另一个。 - 单层逻辑
(t1,t2都不为None)，两个节点值相加，并递归左右子树。
class Solution: def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]: def helper(t1, t2): if t1 is None: return t2 if t2 is None: return t1 t1.val += t2.val t1.left = helper(t1.left, t2.left) t1.right = helper(t1.right, t2.right) return t1 return helper(root1, root2)
700.二叉搜索树中的搜索
在二叉搜索树中找值为val的节点。
利用二叉树的性质（左<根<右）
递归公式：
- 参数：当前节点t。 返回值：节点或None
- 终止条件：t为空
- 单层逻辑：t.val == val,返回。t.val < val ，递归右子树。t.val > val ，递归左子树。
class Solution: def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: def helper(t): if t is None: return None if t.val == val: return t if t.val < val: return helper(t.right) else: return helper(t.left) return helper(root)
98.验证二叉搜索树
利用二叉树的性质（左<根<右）,中序遍历的结果是一个递增的序列。
class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: def inorder(t): if t is None: return inorder(t.left) nums.append(t.val) inorder(t.right) nums = [] inorder(root) return all(nums[i]<nums[i+1] for i in range(len(nums)-1))
530.二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
上面说过，二叉搜索树的中序遍历是一个递增 的，所以差值最小的两个节点一定是在中序遍历过程的相邻的两个节点。
class Solution: def getMinimumDifference(self, root: Optional[TreeNode]) -> int: def inorder(t): if t is None: return inorder(t.left) nums.append(t.val) inorder(t.right) nums = [] inorder(root) return min(nums[i+1] - nums[i] for i in range(len(nums) - 1) )
501.二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
class Solution: def findMode(self, root: Optional[TreeNode]) -> List[int]: def inorder(t): if t is None: return yield from inorder(t.left) yield t.val yield from inorder(t.right) nums = inorder(root) res = [] max_times = 1 cur_times = 1 pre = -10**6 for i, num in enumerate(nums): if num == pre: cur_times += 1 else: pre = num cur_times = 1 if cur_times > max_times: max_times = cur_times res = [num] elif cur_times == max_times: res.append(num) return res
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
我们希望从下往上找两个节点的最近公共祖先，那么二叉树的后序遍历（左右中）就可以实现从下到上的顺序。
递归公式：
- 函数参数：当前节点root, 需要匹配的节点p, q
返回值：如果当前节点是p/q祖先，则返回该节点。如果返回值为空，则表示没找到。 - 终止条件：
当前节点为空或则和p/q匹配，则返回root。 - 单层逻辑
- 递归处理left和right。
如果left和right都不为空，则root为最近公共祖先。
如果left和right只有一个不为空，则返回不为空的那个。
如果left和right都为空，则返回None。
class Solution: def lowestCommonAncestor(self, root, p, q): if root == q or root == p or root is None: return root left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) if left and right: return root if left is None and right: return right elif left and right is None: return left else: return None
235. 二叉搜索树的最近公共祖先
这次找最近公共祖先可以从上到下找了。因为二叉搜索树满足（左<根<右），所以如果root的值在p，q之间，则说明root是p，q的公共祖先（并且是最近的）。
递归公式：
参数：当前节点t
返回值：当前节点t
终止条件：当前节点为None
单层逻辑：如果 t.val 比p，q的值都小，则说明该去右子树找；
如果 t.val 比p，q的值都大，则说明该去左子树找；
否则说明t就是p,q的分叉点，p，q一个在左，一个在右，t就是p,q的最近公共祖先，返回t。
class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': def helper(t): if t is None: return if t.val > p.val and t.val > q.val: return helper(t.left) elif t.val < p.val and t.val < q.val: return helper(t.right) else: return t return helper(root)
701.二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
在二叉树找到空节点插入新数据，不需要调整二叉树结构。
递归公式：
- 参数：当前节点root，待插入的值val
返回值：root - 终止条件：root 为None，创建值为val的节点node并返回node
单层逻辑：
if root.val > val， 递归左子树root.left = self.insertIntoBST(root.left, val)
if root.val < val， 递归右子树root.right = self.insertIntoBST(root.right, val)
返回root
class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]: if not root: node = TreeNode(val) return node if root.val > val: root.left = self.insertIntoBST(root.left, val) if root.val < val: root.right = self.insertIntoBST(root.right, val) return root
450.删除二叉搜索树中的节点
删除二叉搜索树的节点，需要调整树的结构。
递归公式：
- 函数参数： 当前节点root, 待插入值key。
返回值：返回删除后节点后的根节点。 - 终止条件： 当前节点为空，返回None
- 单层逻辑
3.1 如果找到节点(if root.val == key)，删除节点并调整结构。
3.2 没找到节点，则递归查找。
if root.val > key: root.left = self.deleteNode(root.left, key) if root.val < key: root.right = self.deleteNode(root.right, key)
3.3 返回root
其中3.1 删除节点可能遇到多种情况：
- 当前节点没有子节点了，直接删除，返回None
- 当前节点只有单侧节点（左/右），直接删除，返回左/右节点
- 左右节点都有，需要将左子树挂在右子树的最左下角，然后删除节点，返回右节点。
（不需要显式删除节点）
class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]: if root is None: return None if root.val == key: if root.left is None and root.right is None: return None elif root.left is None: return root.right elif root.right is None: return root.left else: # 左右都不为空时， 将 左子树 挂在右子树的最左下角 cur = root.right while cur.left : cur = cur.left cur.left = root.left return root.right if root.val > key: root.left = self.deleteNode(root.left, key) if root.val < key: root.right = self.deleteNode(root.right, key) return root
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。
class Solution: def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]: def helper(t): # 终止条件 if t is None: return None # 单层逻辑 # 1.如果根<low，则（删除根和左孩子），处理右孩子并返回 if t.val < low: right = helper(t.right) return right # 2.同理，如果根>high，则（删除根和右孩子），处理左孩子并返回 if t.val > high: left = helper(t.left) return left # 3.如果结点的值位于区间 [low,high] # 递归处理左，右子树 t.left = helper(t.left) t.right = helper(t.right) return t return helper(root)
108.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从数组中间位置取值作为节点元素，一般不会随机取。所以想构成不平衡的二叉树是自找麻烦。
class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: def helper(left, right): if left > right: return None mid = left + (right-left)//2 root = TreeNode(nums[mid]) root.left = helper(left,mid-1) root.right = helper(mid+1, right) return root return helper(0, len(nums)-1)
538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
二叉搜索树满足左<根<右，所以为了知道比node值大的节点，需要按照 右,根，左的顺序访问（累加）。
class Solution: def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]: pre = 0 # 非局部变量pre，记录上一个（修改过的）节点的值 def traversal(cur): nonlocal pre if cur is None: return # 右 traversal(cur.right) # 根 cur.val += pre pre = cur.val # 左 traversal(cur.left) traversal(root) return root
