.jpg)
538 字
3 分钟
二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
解题思路
- 递归搜索：
- 后序遍历二叉树（左→右→根）
- 若当前节点是 p 或 q，返回该节点
- 递归搜索左右子树
- 结果合并：
- 左右子树均找到节点 → 当前节点为 LCA
- 仅左子树找到 → 返回左子树结果
- 仅右子树找到 → 返回右子树结果
- 基准情况：
- 空节点返回 null
- 找到 p/q 直接返回
关键洞察
- 后序优势：
- 先处理子树再处理根节点
- 自然获取子树搜索结果
- 短路优化：
- 当找到 LCA 时提前终止递归
- 避免无效子树搜索
- 状态传递：
- 非空返回值表示子树存在目标节点
- 双非空返回值确定 LCA 位置
- 单节点处理：
- 当 p/q 是祖先时自动处理
- 无需特殊边界判断
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：每个节点最多访问一次 |
| 空间复杂度 | O(h)：递归栈深度（h为树高，最坏O(n)） |
代码实现
var lowestCommonAncestor = function (root, p, q) { if (!root || root === p || root === q) return root; const left = lowestCommonAncestor(root.left, p, q); const right = lowestCommonAncestor(root.right, p, q); if (left && right) return root; return left || right;};实际应用场景
- 家谱分析：查找两人最近共同祖先`
- 文件系统：查找两个文件最近公共目录`
- 版本控制：查找代码提交的最近共同基线`
- 网络路由：查找两个节点的最近公共路由器`