二叉树-模版题单

• 本质上是图的DFS的一个特例，因此可以用栈来实现

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:preorder = []if root is None:return preorders = [root]while len(s) > 0:node = s.pop()preorder.append(node.val)if node.right is not None:s.append(node.right)if node.left is not None:s.append(node.left)return preorder

class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:s, inorder = [], []node = rootwhile len(s) > 0 or node is not None:if node is not None:s.append(node)node = node.leftelse:node = s.pop()inorder.append(node.val)node = node.rightreturn inorder

class Solution:def postorderTraversal(self, root: TreeNode) -> List[int]:s, postorder = [], []node, last_visit = root, Nonewhile len(s) > 0 or node is not None:if node is not None:s.append(node)node = node.leftelse:peek = s[-1]if peek.right is not None and last_visit != peek.right:node = peek.rightelse:last_visit = s.pop()# 访问过右节点postorder.append(last_visit.val)return postorder

注意点

• 核心就是：根节点必须在右节点弹出之后，再弹出

DFS 深度搜索-从下向上（分治法）

class Solution:def preorderTraversal(self, root: TreeNode) -> List[int]:if root is None:return []left_result = self.preorderTraversal(root.left)right_result = self.preorderTraversal(root.right)return [root.val] + left_result + right_result

注意点：

DFS 深度搜索（从上到下） 和分治法区别：前者一般将最终结果通过指针参数传入，后者一般递归返回结果最后合并

class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:levels = []if root is None:return levelsbfs = collections.deque([root])while len(bfs) > 0:levels.append([])level_size = len(bfs)for _ in range(level_size):node = bfs.popleft()levels[-1].append(node.val)if node.left is not None:bfs.append(node.left)if node.right is not None:bfs.append(node.right)return levels

给定一个二叉树，找出其最大深度。

• 思路 1：分治法

class Solution:def maxDepth(self, root: TreeNode) -> int:if root is None:return 0return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

• 思路 2：层序遍历

class Solution:def maxDepth(self, root: TreeNode) -> List[List[int]]:depth = 0if root is None:return depthbfs = collections.deque([root])while len(bfs) > 0:depth += 1level_size = len(bfs)for _ in range(level_size):node = bfs.popleft()if node.left is not None:bfs.append(node.left)if node.right is not None:bfs.append(node.right)return depth

给定一个二叉树，判断它是否是高度平衡的二叉树。

• 思路 1：分治法，左边平衡 && 右边平衡 && 左右两边高度 <= 1，

class Solution:def isBalanced(self, root: TreeNode) -> bool:def depth(root):if root is None:return 0, Truedl, bl = depth(root.left)dr, br = depth(root.right)return max(dl, dr) + 1, bl and br and abs(dl - dr) < 2_, out = depth(root)return out

• 思路 2：使用后序遍历实现分治法的迭代版本

class Solution:def isBalanced(self, root: TreeNode) -> bool:s = [[TreeNode(), -1, -1]]node, last = root, Nonewhile len(s) > 1 or node is not None:if node is not None:s.append([node, -1, -1])node = node.leftif node is None:s[-1][1] = 0else:peek = s[-1][0]if peek.right is not None and last != peek.right:node = peek.rightelse:if peek.right is None:s[-1][2] = 0last, dl, dr = s.pop()if abs(dl - dr) > 1:return Falsed = max(dl, dr) + 1if s[-1][1] == -1:s[-1][1] = delse:s[-1][2] = dreturn True

给定一个非空二叉树，返回其最大路径和。

• 思路：分治法。最大路径的可能情况：左子树的最大路径，右子树的最大路径，或通过根结点的最大路径。其中通过根结点的最大路径值等于以左子树根结点为端点的最大路径值加以右子树根结点为端点的最大路径值再加上根结点值，这里还要考虑有负值的情况即负值路径需要丢弃不取。

class Solution:def maxPathSum(self, root: TreeNode) -> int:self.maxPath = float('-inf')def largest_path_ends_at(node):if node is None:return float('-inf')e_l = largest_path_ends_at(node.left)e_r = largest_path_ends_at(node.right)self.maxPath = max(self.maxPath, node.val + max(0, e_l) + max(0, e_r), e_l, e_r)return node.val + max(e_l, e_r, 0)largest_path_ends_at(root)return self.maxPath

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

• 思路：分治法，有左子树的公共祖先或者有右子树的公共祖先，就返回子树的祖先，否则返回根节点

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root is None:return Noneif root == p or root == q:return rootleft = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left is not None and right is not None:return rootelif left is not None:return leftelif right is not None:return rightelse:return None

给定一个二叉树，返回其节点值的锯齿形层次遍历。Z 字形遍历

• 思路：在BFS迭代模板上改用双端队列控制输出顺序

class Solution:def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:levels = []if root is None:return levelss = collections.deque([root])start_from_left = Truewhile len(s) > 0:levels.append([])level_size = len(s)if start_from_left:for _ in range(level_size):node = s.popleft()levels[-1].append(node.val)if node.left is not None:s.append(node.left)if node.right is not None:s.append(node.right)else:for _ in range(level_size):node = s.pop()levels[-1].append(node.val)if node.right is not None:s.appendleft(node.right)if node.left is not None:s.appendleft(node.left)start_from_left = not start_from_leftreturn levels

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

• 思路 1：中序遍历后检查输出是否有序，缺点是如果不平衡无法提前返回结果， 代码略

• 思路 2：分治法，一个二叉树为合法的二叉搜索树当且仅当左右子树为合法二叉搜索树且根结点值大于右子树最小值小于左子树最大值。缺点是若不用迭代形式实现则无法提前返回，而迭代实现右比较复杂。

class Solution:def isValidBST(self, root: TreeNode) -> bool:if root is None: return Truedef valid_min_max(node):isValid = Trueif node.left is not None:l_isValid, l_min, l_max = valid_min_max(node.left)isValid = isValid and node.val > l_maxelse:l_isValid, l_min = True, node.valif node.right is not None:r_isValid, r_min, r_max = valid_min_max(node.right)isValid = isValid and node.val < r_minelse:r_isValid, r_max = True, node.valreturn l_isValid and r_isValid and isValid, l_min, r_maxreturn valid_min_max(root)[0]

• 思路 3：利用二叉搜索树的性质，根结点为左子树的右边界，右子树的左边界，使用先序遍历自顶向下更新左右子树的边界并检查是否合法，迭代版本实现简单且可以提前返回结果。

class Solution:def isValidBST(self, root: TreeNode) -> bool:if root is None:return Trues = [(root, float('-inf'), float('inf'))]while len(s) > 0:node, low, up = s.pop()if node.left is not None:if node.left.val <= low or node.left.val >= node.val:return Falses.append((node.left, low, node.val))if node.right is not None:if node.right.val <= node.val or node.right.val >= up:return Falses.append((node.right, node.val, up))return True

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。

• 思路：如果只是为了完成任务则找到最后一个叶子节点满足插入条件即可。但此题深挖可以涉及到如何插入并维持平衡二叉搜索树的问题，并不适合初学者。

class Solution:def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:if root is None:return TreeNode(val)node = rootwhile True:if val > node.val:if node.right is None:node.right = TreeNode(val)return rootelse:node = node.rightelse:if node.left is None:node.left = TreeNode(val)return rootelse:node = node.left