LeetCode 236. 二叉树的最近公共祖先：深度优先搜索的应用

LeetCode 236. 二叉树的最近公共祖先深度优先搜索的应用问题描述给定一个二叉树找到该树中两个指定节点的最近公共祖先。示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1 输出3示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4 输出5示例 3输入root [1,2], p 1, q 2 输出1算法原理核心思路二叉树的最近公共祖先问题可以通过深度优先搜索DFS来解决其核心思想是从根节点开始递归地遍历左右子树如果当前节点是 p 或 q返回当前节点递归地在左子树和右子树中查找 p 和 q如果左子树和右子树都找到了 p 和 q那么当前节点就是最近公共祖先如果只有左子树找到了 p 或 q返回左子树的结果如果只有右子树找到了 p 或 q返回右子树的结果复杂度分析时间复杂度O(n)其中 n 是二叉树的节点数。每个节点恰好被访问一次。空间复杂度O(h)其中 h 是二叉树的高度。递归调用栈的深度最大为 h。代码实现# Definition for a binary tree node. class TreeNode: def __init__(self, x): self.val x self.left None self.right None class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: # 如果根节点为空返回 None if not root: return None # 如果当前节点是 p 或 q返回当前节点 if root p or root q: return root # 递归地在左子树和右子树中查找 p 和 q left self.lowestCommonAncestor(root.left, p, q) right self.lowestCommonAncestor(root.right, p, q) # 如果左子树和右子树都找到了 p 和 q那么当前节点就是最近公共祖先 if left and right: return root # 如果只有左子树找到了 p 或 q返回左子树的结果 if left: return left # 如果只有右子树找到了 p 或 q返回右子树的结果 return right代码解析边界处理如果根节点为None返回None。节点检查如果当前节点是 p 或 q返回当前节点。递归查找递归地在左子树和右子树中查找 p 和 q。结果判断如果左子树和右子树都找到了 p 和 q那么当前节点就是最近公共祖先。如果只有左子树找到了 p 或 q返回左子树的结果。如果只有右子树找到了 p 或 q返回右子树的结果。实战技巧递归思想自底向上从叶子节点开始向上查找 p 和 q 的最近公共祖先。状态传递通过返回值传递查找状态左子树和右子树的查找结果会传递给父节点。边界条件处理空树如果树为空返回None。节点在根节点如果其中一个节点是根节点那么根节点就是最近公共祖先。错误分析常见错误递归终止条件错误忘记处理节点为None的情况导致递归无法终止。节点比较错误使用节点值而不是节点引用进行比较导致错误。逻辑判断错误在处理左子树和右子树的查找结果时逻辑判断错误。扩展思考变种问题二叉搜索树的最近公共祖先利用二叉搜索树的特性优化查找过程。N 叉树的最近公共祖先将二叉树扩展为 N 叉树查找最近公共祖先。多个节点的最近公共祖先查找多个节点的最近公共祖先。应用场景最近公共祖先问题在以下场景中有着广泛的应用树的操作在树结构中查找节点之间的关系。基因alogy在家族树中查找共同祖先。网络分析在网络拓扑中查找节点之间的关系。个人实践感悟最近在准备转正答辩每天被各种算法题和合并冲突吓醒救命今天刷到这个经典的最近公共祖先问题突然想到刚实习时第一次写这个题的场景。当时我还不知道递归的正确逻辑结果代码在测试用例 [3,5,1,6,2,0,8,null,null,7,4] 上失败了被mentor嘲笑了一整天麻了现在再看这个问题其实关键在于正确的递归逻辑。需要从叶子节点开始向上查找 p 和 q 的最近公共祖先。当左子树和右子树都找到了 p 和 q 时当前节点就是最近公共祖先。这让我意识到算法的学习真的是一个循序渐进的过程从一无所知到熟练掌握需要不断地练习和总结。最后分享一个小技巧在面试中遇到最近公共祖先问题首先要想到递归实现同时要注意正确的递归逻辑和边界条件处理。如果是二叉搜索树可以利用其特性进行优化。这就是大佬吗我也要成为这样的人输入输出示例输入输出示例 1输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 1输出3输入输出示例 2输入root [3,5,1,6,2,0,8,null,null,7,4], p 5, q 4输出5输入输出示例 3输入root [1,2], p 1, q 2输出1结语二叉树的最近公共祖先问题是树算法中的经典问题掌握它不仅有助于解决相关的LeetCode问题也能帮助我们更好地理解深度优先搜索的思想。希望这篇文章对大家有所帮助祝大家刷题愉快