LeetCode 1123. 最深叶节点的最近公共祖先
题目描述
题意分析
找出整棵树中深度最大的所有叶节点，再返回包含这些叶节点的最深公共祖先。如果最深叶只有一个，它自身就是答案。
当前子树的最深叶来自左边、右边还是两边，取决于左右子树的高度。因而递归不必保存全部叶节点，只需同时返回子树高度和其中最深叶的最近公共祖先，再由父节点合并这两份信息。
解法：后序遍历返回深度和候选节点
核心思路
[!blue]
dfs(node)返回一对结果：depth是从当前节点向下计算的子树高度，node字段是这棵子树最深叶的最近公共祖先。这里的高度按节点数计，空树为零、叶节点为一；它不是题面中从整棵树根开始计算的绝对深度。先递归取得左右结果，再分三种情况合并：
- 左侧更高：当前子树最深的叶节点全部在左子树，右边没有同样深的叶节点，因此直接继承左侧候选。
- 右侧更高：同理继承右侧候选。
- 两侧同高且非空：两边都含有当前子树的最深叶，任何严格位于左侧或右侧的节点都无法同时包含另一边的叶子，因此当前节点恰好是最近公共祖先。两侧高度都为零时，当前节点是叶子，候选也自然是它自身。
无论候选来自哪里，返回的高度都必须是较大子树高度加一，供上一层继续比较。空节点返回
(空, 0)，每个非空节点都在孩子结果正确的基础上作出上述合并，因此最外层返回的候选就是整棵树的答案。
解题步骤
- 后序取得左右两份结果。
- 比较高度选择当前节点或较深一侧候选。
- 高度加一继续返回，入口取候选字段。
代码实现
class Solution {
public TreeNode lcaDeepestLeaves(TreeNode root) {
return dfs(root).node;
}
private Result dfs(TreeNode node) {
if (node == null) {
return new Result(null, 0);
}
Result left = dfs(node.left);
Result right = dfs(node.right);
// 两侧同高时取当前节点，叶子两侧为空也自然适用。
if (left.depth == right.depth) {
return new Result(node, left.depth + 1);
}
if (left.depth > right.depth) {
// 最深叶全在左侧，继承其候选，但当前子树高度加一。
return new Result(left.node, left.depth + 1);
}
return new Result(right.node, right.depth + 1);
}
private static class Result {
private final TreeNode node;
private final int depth;
Result(TreeNode node, int depth) {
this.node = node;
this.depth = depth;
}
}
}
func lcaDeepestLeaves(root *TreeNode) *TreeNode {
node, _ := dfs(root)
return node
}
func dfs(node *TreeNode) (*TreeNode, int) {
if node == nil {
return nil, 0
}
leftNode, leftDepth := dfs(node.Left)
rightNode, rightDepth := dfs(node.Right)
// 两侧同高时取当前节点，叶子两侧为空也自然适用。
if leftDepth == rightDepth {
return node, leftDepth + 1
}
if leftDepth > rightDepth {
// 最深叶全在左侧，继承其候选，但当前子树高度加一。
return leftNode, leftDepth + 1
}
return rightNode, rightDepth + 1
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点只访问一次，合并左右结果只需常数次比较。
- 空间复杂度：$O(h)$，其中 $h$ 是树高，包含递归栈与仍需使用的返回记录；树退化为链时为 $O(n)$。
关键点总结
[!green]
- 这里的高度相对子树根，不是相对整棵树根的绝对深度。
- 叶子的两边为空时，相等分支返回叶子自身。
易错点总结
[!yellow]
- 高度不等仍返回当前节点，会把祖先抬得过高。
- 继承一侧候选却使用另一侧高度，会误导更高层。
- 高度相等时只返回左候选，无法覆盖右侧同深叶子。
- 只有一个最深叶时，应一路保留这个叶子作为候选；它本身也是自己的祖先，不需要再向父节点抬一层。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 236. 二叉树的最近公共祖先 | 中等 | 把两个指定节点的最近公共祖先扩展为全部最深叶子，可后序合并深度与祖先。 |
| 104. 二叉树的最大深度 | 简单 | 比较左右子树高度后，较深一侧提供答案，同高时当前根成为共同祖先。 |
| 865. 具有所有最深节点的最小子树 | 中等 | 递归向上传递目标命中信息；本题合并最深层深度与祖先信息，该题定位包含所有最深节点的最小子树。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！