1. 二叉搜索树与二叉树算法精讲今天要讨论的三个题目都是二叉树类算法中的经典问题涵盖了二叉搜索树(BST)和普通二叉树的重要操作。二叉搜索树因其有序特性在算法题中经常出现而最近公共祖先(LCA)问题则是二叉树遍历的典型应用。这三个题目看似独立实则都涉及二叉树的遍历和特性应用。530题考察BST的中序遍历特性501题需要统计节点值频率236题则需要处理普通二叉树的递归关系。掌握这些题目能帮助我们建立对树形数据结构的系统认知。提示在开始前请确保已经掌握二叉树的前序、中序、后序遍历的递归和非递归写法这是解决所有树相关问题的基础。1.1 二叉搜索树的最小绝对差BST的中序遍历结果是一个有序数组这个特性是解决530题的关键。我们需要找到树中任意两节点值差的最小值。最直观的思路是中序遍历得到有序数组遍历数组计算相邻元素的差值找出最小差值但这样需要O(n)额外空间。更优的解法是在中序遍历过程中记录前驱节点实时计算差值class Solution: def getMinimumDifference(self, root: TreeNode) - int: self.prev None self.min_diff float(inf) def inorder(node): if not node: return inorder(node.left) if self.prev is not None: self.min_diff min(self.min_diff, node.val - self.prev) self.prev node.val inorder(node.right) inorder(root) return self.min_diff这个解法的时间复杂度是O(n)空间复杂度是O(h)h为树高。相比先存储整个遍历结果空间效率更高。注意BST的中序遍历结果一定是升序的所以只需比较相邻节点差值即可。如果是普通二叉树则需要考虑所有节点对复杂度会变为O(n²)。1.2 二叉搜索树中的众数501题要求找出BST中出现频率最高的元素。BST的有序性再次发挥作用相同值的节点必然连续出现在中序遍历中。统计频率的步骤中序遍历BST比较当前节点值与前一节点值如果相同则增加当前计数否则重置计数维护最大频率和结果列表class Solution: def findMode(self, root: TreeNode) - List[int]: self.current_val None self.current_count 0 self.max_count 0 self.result [] def inorder(node): if not node: return inorder(node.left) if node.val self.current_val: self.current_count 1 else: self.current_val node.val self.current_count 1 if self.current_count self.max_count: self.max_count self.current_count self.result [node.val] elif self.current_count self.max_count: self.result.append(node.val) inorder(node.right) inorder(root) return self.result这个解法同样利用了BST的中序特性时间复杂度O(n)空间复杂度O(h)。如果BST中有多个众数都能被正确找出。实操心得在遍历过程中维护状态变量(current_val, current_count等)是处理这类问题的常用技巧可以避免存储整个遍历结果。2. 二叉树的最近公共祖先236题是二叉树算法中的经典问题要求找出两个节点的最近公共祖先。这个问题在实际开发中有很多应用场景比如Git中寻找两个分支的最近共同提交。2.1 递归解法递归是解决树问题的自然思路。对于当前节点有三种情况p和q分别在左右子树中当前节点就是LCA只有p或q在子树中返回找到的节点都没找到返回Noneclass Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right这个解法的时间复杂度是O(n)最坏情况下需要遍历所有节点。空间复杂度是O(h)由递归栈深度决定。2.2 迭代解法虽然递归解法简洁但理解其工作原理很重要。我们可以用迭代方式模拟这个过程使用父指针哈希表记录每个节点的父节点从p节点向上回溯记录访问过的祖先节点从q节点向上回溯第一个遇到的公共祖先就是LCAclass Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: stack [root] parent {root: None} while p not in parent or q not in parent: node stack.pop() if node.left: parent[node.left] node stack.append(node.left) if node.right: parent[node.right] node stack.append(node.right) ancestors set() while p: ancestors.add(p) p parent[p] while q not in ancestors: q parent[q] return q这个解法同样需要O(n)时间和空间但避免了递归可能导致的栈溢出问题。注意事项迭代解法在树很大时更可靠但代码相对复杂。面试时可以先给出递归解法再讨论迭代优化。3. 算法优化与变种问题3.1 BST最小绝对差的优化530题还可以用Morris遍历实现O(1)空间复杂度。Morris遍历利用叶子节点的空指针实现无栈遍历class Solution: def getMinimumDifference(self, root: TreeNode) - int: prev None min_diff float(inf) curr root while curr: if not curr.left: if prev is not None: min_diff min(min_diff, curr.val - prev) prev curr.val curr curr.right else: predecessor curr.left while predecessor.right and predecessor.right ! curr: predecessor predecessor.right if not predecessor.right: predecessor.right curr curr curr.left else: predecessor.right None if prev is not None: min_diff min(min_diff, curr.val - prev) prev curr.val curr curr.right return min_diffMorris遍历虽然节省空间但会修改树结构(临时添加指针)且常数因子较大在实际应用中需要权衡。3.2 普通二叉树的众数问题如果501题的输入是普通二叉树解法会有所不同。我们需要遍历整个树统计所有值的频率from collections import defaultdict class Solution: def findMode(self, root: TreeNode) - List[int]: freq defaultdict(int) def traverse(node): if not node: return freq[node.val] 1 traverse(node.left) traverse(node.right) traverse(root) max_freq max(freq.values()) if freq else 0 return [k for k, v in freq.items() if v max_freq]这个解法需要O(n)时间和空间适用于任何二叉树。相比BST专用解法它更通用但效率略低。3.3 LCA问题的扩展236题有一些有趣的变种带父指针的树可以直接向上回溯无需哈希表多次查询可以预处理每个节点的深度加速查询N叉树的LCA递归逻辑类似需要考虑所有子节点例如带父指针的解法def lowestCommonAncestor(p: Node, q: Node) - Node: def getDepth(node): depth 0 while node: node node.parent depth 1 return depth p_depth getDepth(p) q_depth getDepth(q) while p_depth q_depth: p p.parent p_depth - 1 while q_depth p_depth: q q.parent q_depth - 1 while p ! q: p p.parent q q.parent return p这个解法时间复杂度是O(h)空间复杂度O(1)效率更高但需要树节点存储父指针。4. 常见问题与调试技巧4.1 BST遍历中的易错点在处理530和501题时常见错误包括忘记处理空树情况中序遍历时更新前驱节点的时机不对频率统计时没有正确处理第一个节点调试建议打印中序遍历结果验证顺序是否正确在更新min_diff或max_count时打印相关变量使用小型测试用例(如[1,null,2])逐步验证4.2 LCA问题的边界条件236题需要特别注意p或q为None的情况p或q不在树中的情况p就是q的情况p或q是根节点的情况完善的解法应该处理这些边界条件class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: self.found_p False self.found_q False def dfs(node): if not node: return None left dfs(node.left) right dfs(node.right) if node p: self.found_p True return node if node q: self.found_q True return node if left and right: return node return left if left else right result dfs(root) return result if self.found_p and self.found_q else None这个版本会检查p和q是否都在树中如果不在则返回None。4.3 性能优化实践对于大规模树结构可以考虑以下优化使用迭代而非递归避免栈溢出对于多次查询的LCA问题使用Tarjan离线算法或二进制提升在统计众数时对于BST优先使用中序遍历特性例如使用栈实现的中序遍历def findMode(root): stack [] curr root current_val None current_count 0 max_count 0 result [] while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() if curr.val current_val: current_count 1 else: current_val curr.val current_count 1 if current_count max_count: max_count current_count result [current_val] elif current_count max_count: result.append(current_val) curr curr.right return result这个版本避免了递归深度限制适合处理非常深的BST。 二叉搜索树与二叉树算法精讲：遍历、LCA与优化技巧
1. 二叉搜索树与二叉树算法精讲今天要讨论的三个题目都是二叉树类算法中的经典问题涵盖了二叉搜索树(BST)和普通二叉树的重要操作。二叉搜索树因其有序特性在算法题中经常出现而最近公共祖先(LCA)问题则是二叉树遍历的典型应用。这三个题目看似独立实则都涉及二叉树的遍历和特性应用。530题考察BST的中序遍历特性501题需要统计节点值频率236题则需要处理普通二叉树的递归关系。掌握这些题目能帮助我们建立对树形数据结构的系统认知。提示在开始前请确保已经掌握二叉树的前序、中序、后序遍历的递归和非递归写法这是解决所有树相关问题的基础。1.1 二叉搜索树的最小绝对差BST的中序遍历结果是一个有序数组这个特性是解决530题的关键。我们需要找到树中任意两节点值差的最小值。最直观的思路是中序遍历得到有序数组遍历数组计算相邻元素的差值找出最小差值但这样需要O(n)额外空间。更优的解法是在中序遍历过程中记录前驱节点实时计算差值class Solution: def getMinimumDifference(self, root: TreeNode) - int: self.prev None self.min_diff float(inf) def inorder(node): if not node: return inorder(node.left) if self.prev is not None: self.min_diff min(self.min_diff, node.val - self.prev) self.prev node.val inorder(node.right) inorder(root) return self.min_diff这个解法的时间复杂度是O(n)空间复杂度是O(h)h为树高。相比先存储整个遍历结果空间效率更高。注意BST的中序遍历结果一定是升序的所以只需比较相邻节点差值即可。如果是普通二叉树则需要考虑所有节点对复杂度会变为O(n²)。1.2 二叉搜索树中的众数501题要求找出BST中出现频率最高的元素。BST的有序性再次发挥作用相同值的节点必然连续出现在中序遍历中。统计频率的步骤中序遍历BST比较当前节点值与前一节点值如果相同则增加当前计数否则重置计数维护最大频率和结果列表class Solution: def findMode(self, root: TreeNode) - List[int]: self.current_val None self.current_count 0 self.max_count 0 self.result [] def inorder(node): if not node: return inorder(node.left) if node.val self.current_val: self.current_count 1 else: self.current_val node.val self.current_count 1 if self.current_count self.max_count: self.max_count self.current_count self.result [node.val] elif self.current_count self.max_count: self.result.append(node.val) inorder(node.right) inorder(root) return self.result这个解法同样利用了BST的中序特性时间复杂度O(n)空间复杂度O(h)。如果BST中有多个众数都能被正确找出。实操心得在遍历过程中维护状态变量(current_val, current_count等)是处理这类问题的常用技巧可以避免存储整个遍历结果。2. 二叉树的最近公共祖先236题是二叉树算法中的经典问题要求找出两个节点的最近公共祖先。这个问题在实际开发中有很多应用场景比如Git中寻找两个分支的最近共同提交。2.1 递归解法递归是解决树问题的自然思路。对于当前节点有三种情况p和q分别在左右子树中当前节点就是LCA只有p或q在子树中返回找到的节点都没找到返回Noneclass Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root or root p or root q: return root left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) if left and right: return root return left if left else right这个解法的时间复杂度是O(n)最坏情况下需要遍历所有节点。空间复杂度是O(h)由递归栈深度决定。2.2 迭代解法虽然递归解法简洁但理解其工作原理很重要。我们可以用迭代方式模拟这个过程使用父指针哈希表记录每个节点的父节点从p节点向上回溯记录访问过的祖先节点从q节点向上回溯第一个遇到的公共祖先就是LCAclass Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: stack [root] parent {root: None} while p not in parent or q not in parent: node stack.pop() if node.left: parent[node.left] node stack.append(node.left) if node.right: parent[node.right] node stack.append(node.right) ancestors set() while p: ancestors.add(p) p parent[p] while q not in ancestors: q parent[q] return q这个解法同样需要O(n)时间和空间但避免了递归可能导致的栈溢出问题。注意事项迭代解法在树很大时更可靠但代码相对复杂。面试时可以先给出递归解法再讨论迭代优化。3. 算法优化与变种问题3.1 BST最小绝对差的优化530题还可以用Morris遍历实现O(1)空间复杂度。Morris遍历利用叶子节点的空指针实现无栈遍历class Solution: def getMinimumDifference(self, root: TreeNode) - int: prev None min_diff float(inf) curr root while curr: if not curr.left: if prev is not None: min_diff min(min_diff, curr.val - prev) prev curr.val curr curr.right else: predecessor curr.left while predecessor.right and predecessor.right ! curr: predecessor predecessor.right if not predecessor.right: predecessor.right curr curr curr.left else: predecessor.right None if prev is not None: min_diff min(min_diff, curr.val - prev) prev curr.val curr curr.right return min_diffMorris遍历虽然节省空间但会修改树结构(临时添加指针)且常数因子较大在实际应用中需要权衡。3.2 普通二叉树的众数问题如果501题的输入是普通二叉树解法会有所不同。我们需要遍历整个树统计所有值的频率from collections import defaultdict class Solution: def findMode(self, root: TreeNode) - List[int]: freq defaultdict(int) def traverse(node): if not node: return freq[node.val] 1 traverse(node.left) traverse(node.right) traverse(root) max_freq max(freq.values()) if freq else 0 return [k for k, v in freq.items() if v max_freq]这个解法需要O(n)时间和空间适用于任何二叉树。相比BST专用解法它更通用但效率略低。3.3 LCA问题的扩展236题有一些有趣的变种带父指针的树可以直接向上回溯无需哈希表多次查询可以预处理每个节点的深度加速查询N叉树的LCA递归逻辑类似需要考虑所有子节点例如带父指针的解法def lowestCommonAncestor(p: Node, q: Node) - Node: def getDepth(node): depth 0 while node: node node.parent depth 1 return depth p_depth getDepth(p) q_depth getDepth(q) while p_depth q_depth: p p.parent p_depth - 1 while q_depth p_depth: q q.parent q_depth - 1 while p ! q: p p.parent q q.parent return p这个解法时间复杂度是O(h)空间复杂度O(1)效率更高但需要树节点存储父指针。4. 常见问题与调试技巧4.1 BST遍历中的易错点在处理530和501题时常见错误包括忘记处理空树情况中序遍历时更新前驱节点的时机不对频率统计时没有正确处理第一个节点调试建议打印中序遍历结果验证顺序是否正确在更新min_diff或max_count时打印相关变量使用小型测试用例(如[1,null,2])逐步验证4.2 LCA问题的边界条件236题需要特别注意p或q为None的情况p或q不在树中的情况p就是q的情况p或q是根节点的情况完善的解法应该处理这些边界条件class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: self.found_p False self.found_q False def dfs(node): if not node: return None left dfs(node.left) right dfs(node.right) if node p: self.found_p True return node if node q: self.found_q True return node if left and right: return node return left if left else right result dfs(root) return result if self.found_p and self.found_q else None这个版本会检查p和q是否都在树中如果不在则返回None。4.3 性能优化实践对于大规模树结构可以考虑以下优化使用迭代而非递归避免栈溢出对于多次查询的LCA问题使用Tarjan离线算法或二进制提升在统计众数时对于BST优先使用中序遍历特性例如使用栈实现的中序遍历def findMode(root): stack [] curr root current_val None current_count 0 max_count 0 result [] while curr or stack: while curr: stack.append(curr) curr curr.left curr stack.pop() if curr.val current_val: current_count 1 else: current_val curr.val current_count 1 if current_count max_count: max_count current_count result [current_val] elif current_count max_count: result.append(current_val) curr curr.right return result这个版本避免了递归深度限制适合处理非常深的BST。