二叉树算法解析：从基础遍历到LeetCode Hot100实战

1. 二叉树基础与Hot100算法概述二叉树作为数据结构领域的核心基础在算法面试和实际工程中占据着不可替代的地位。最近在整理LeetCode Hot100题目时我发现二叉树相关题目出现频率极高几乎每10道经典题中就包含2-3道二叉树问题。这促使我系统梳理了二叉树在算法题中的常见考察点和解题范式。二叉树本质上是由节点组成的层次结构每个节点最多有两个子节点左子节点和右子节点。这种看似简单的结构却能衍生出前序、中序、后序三种深度优先遍历方式以及层序遍历这种广度优先遍历方式。在实际解题时选择哪种遍历方式往往决定了代码的简洁性和效率。提示二叉树问题在面试中常作为中等难度题目出现主要考察应聘者对递归和迭代的理解程度以及对边界条件的处理能力。2. 二叉树遍历的核心算法实现2.1 深度优先遍历的递归实现递归是解决二叉树问题最直观的方法。以中序遍历为例其递归实现遵循左-根-右的顺序def inorderTraversal(root): res [] def dfs(node): if not node: return dfs(node.left) # 先遍历左子树 res.append(node.val) # 访问根节点 dfs(node.right) # 最后遍历右子树 dfs(root) return res这种写法虽然简洁但在实际面试中需要注意两个问题一是递归深度过大可能导致栈溢出虽然二叉树问题通常不会二是要能准确说出时间和空间复杂度均为O(n)。2.2 迭代实现的关键技巧迭代法通常使用栈来模拟递归过程。还是以中序遍历为例def inorderTraversal(root): res [] stack [] curr root while curr or stack: while curr: # 将左子节点全部入栈 stack.append(curr) curr curr.left curr stack.pop() # 弹出最左侧节点 res.append(curr.val) # 访问节点值 curr curr.right # 转向右子树 return res迭代法的优势在于可以避免递归的系统开销但代码逻辑相对复杂。在Hot100题目中像94. 二叉树的中序遍历这类基础题目面试官往往会要求同时给出递归和迭代两种解法。3. Hot100高频题型解析3.1 对称二叉树问题101题判断二叉树是否对称是经典的递归应用场景def isSymmetric(root): def check(left, right): if not left and not right: return True if not left or not right: return False return (left.val right.val and check(left.left, right.right) and check(left.right, right.left)) return check(root.left, root.right) if root else True这道题的解题关键在于理解对称的定义左右子树必须是镜像关系。在实际编码时容易犯的错误是只比较了左右子节点的值而忽略了子树结构。3.2 二叉树的最大深度104题求最大深度可以通过递归轻松实现def maxDepth(root): if not root: return 0 return max(maxDepth(root.left), maxDepth(root.right)) 1这个简单的递归蕴含着分治思想二叉树的最大深度等于左右子树最大深度中的较大者加1。迭代法则可以使用层序遍历记录遍历的层数。4. 层序遍历的变种与应用4.1 基本的层序遍历实现层序遍历又称广度优先遍历需要借助队列实现from collections import deque def levelOrder(root): if not root: return [] queue deque([root]) res [] while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(level) return res这种写法在解决102. 二叉树的层序遍历时是标准解法。值得注意的是内层循环使用level_size来区分不同层级的节点这是处理层序遍历问题的关键技巧。4.2 锯齿形层序遍历103题在基本层序遍历基础上稍作修改即可实现锯齿形遍历def zigzagLevelOrder(root): if not root: return [] queue deque([root]) res [] left_to_right True while queue: level_size len(queue) level deque() for _ in range(level_size): node queue.popleft() if left_to_right: level.append(node.val) else: level.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) res.append(list(level)) left_to_right not left_to_right return res这里使用双端队列并在每层结束后改变添加方向是解决这类变种问题的通用方法。5. 二叉树构造问题5.1 从前序与中序遍历序列构造二叉树105题这是典型的二叉树构造问题需要理解遍历序列的特点def buildTree(preorder, inorder): if not preorder or not inorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(preorder[1:idx1], inorder[:idx]) root.right buildTree(preorder[idx1:], inorder[idx1:]) return root前序序列的第一个元素总是根节点而中序序列中根节点左侧是左子树右侧是右子树。通过这个特点可以递归构建整棵树。在实际应用中为了提高效率通常会先用哈希表存储中序序列的值和索引。5.2 从后序与中序遍历序列构造二叉树106题类似地后序序列的最后一个元素是根节点def buildTree(inorder, postorder): if not inorder or not postorder: return None root_val postorder[-1] root TreeNode(root_val) idx inorder.index(root_val) root.left buildTree(inorder[:idx], postorder[:idx]) root.right buildTree(inorder[idx1:], postorder[idx:-1]) return root这类问题的关键在于找准根节点位置并正确划分左右子树的区间。在面试中面试官可能会要求解释为什么需要中序序列配合前序或后序序列才能唯一确定二叉树结构。6. 二叉搜索树特性应用6.1 验证二叉搜索树98题利用二叉搜索树的中序遍历是升序序列这一特性def isValidBST(root): prev float(-inf) stack [] curr root while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() if curr.val prev: return False prev curr.val curr curr.right return True这道题常见的错误是只检查当前节点与左右子节点的关系而忽略了整个左子树都必须小于根节点这一全局条件。使用中序遍历可以巧妙地避免这个问题。6.2 二叉搜索树中的搜索700题利用BST的性质可以高效搜索def searchBST(root, val): while root: if root.val val: return root root root.left if val root.val else root.right return NoneBST的搜索效率是O(h)其中h是树的高度。对于平衡的BST这个复杂度可以降到O(log n)。7. 二叉树路径问题7.1 路径总和112题检查是否存在从根到叶子的路径和等于给定值def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return root.val targetSum return (hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val))这类问题的关键在于正确处理叶子节点的判断条件。在递归过程中递减目标值到达叶子节点时检查剩余值是否等于节点值。7.2 二叉树中的最大路径和124题更复杂的路径问题需要考虑路径不一定经过根节点def maxPathSum(root): max_sum float(-inf) def helper(node): nonlocal max_sum if not node: return 0 left max(helper(node.left), 0) right max(helper(node.right), 0) max_sum max(max_sum, left right node.val) return max(left, right) node.val helper(root) return max_sum这道hard题目需要理解路径的多种可能情况可能是左子树路径当前节点右子树路径也可能是左或右子树的单边路径。helper函数返回的是以当前节点为端点的最大单边路径和。8. 特殊二叉树问题8.1 翻转二叉树226题经典的递归应用def invertTree(root): if root: root.left, root.right invertTree(root.right), invertTree(root.left) return root这道题看似简单却能很好地考察对递归的理解。迭代法可以使用层序遍历在访问每个节点时交换其左右子节点。8.2 二叉树的直径543题直径定义为任意两节点间最长路径的长度def diameterOfBinaryTree(root): diameter 0 def depth(node): nonlocal diameter if not node: return 0 left depth(node.left) right depth(node.right) diameter max(diameter, left right) return max(left, right) 1 depth(root) return diameter解题关键在于理解直径不一定经过根节点可能是任意两个叶子节点之间的最长路径。在计算节点深度的同时更新最大直径。9. 二叉树序列化问题9.1 二叉树的序列化与反序列化297题将二叉树转换为字符串表示def serialize(root): if not root: return null return (str(root.val) , serialize(root.left) , serialize(root.right)) def deserialize(data): def helper(nodes): val next(nodes) if val null: return None node TreeNode(int(val)) node.left helper(nodes) node.right helper(nodes) return node return helper(iter(data.split(,)))这里使用前序遍历进行序列化因为可以方便地第一个元素就是根节点。在实际应用中还需要考虑如何处理大数据量的情况。10. 二叉树最近公共祖先问题10.1 二叉树的最近公共祖先236题寻找两个节点的最低公共祖先def lowestCommonAncestor(root, p, q): if not root or root p or root q: return root left lowestCommonAncestor(root.left, p, q) right lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right这道题的解法基于后序遍历当在左右子树中分别找到p和q时当前节点就是LCA。对于BST版本235题可以利用BST的性质进行优化。