最深叶节点的最近公共祖先
难度:
标签:
题目描述
给你一个有根节点 root 的二叉树，返回它 最深的叶节点的最近公共祖先 。
回想一下：
- 叶节点 是二叉树中没有子节点的节点
- 树的根节点的 深度 为
0，如果某一节点的深度为d，那它的子节点的深度就是d+1 - 如果我们假定
A是一组节点S的 最近公共祖先，S中的每个节点都在以A为根节点的子树中，且A的深度达到此条件下可能的最大值。
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4] 解释：我们返回值为 2 的节点，在图中用黄色标记。 在图中用蓝色标记的是树的最深的节点。 注意，节点 6、0 和 8 也是叶节点，但是它们的深度是 2 ，而节点 7 和 4 的深度是 3 。
示例 2：
输入：root = [1] 输出：[1] 解释：根节点是树中最深的节点，它是它本身的最近公共祖先。
示例 3：
输入：root = [0,1,3,null,2] 输出：[2] 解释：树中最深的叶节点是 2 ，最近公共祖先是它自己。
提示：
- 树中的节点数将在
[1, 1000]的范围内。 0 <= Node.val <= 1000- 每个节点的值都是 独一无二 的。
注意：本题与力扣 865 重复：https://leetcode-cn.com/problems/smallest-subtree-with-all-the-deepest-nodes/
代码结果
运行时间: 29 ms, 内存: 16.4 MB
/*
* 思路：
* 1. 使用递归计算每个节点的深度。
* 2. 找到所有最深的叶节点。
* 3. 使用Java Stream API来简化部分计算。
*/
import java.util.*;
import java.util.stream.*;
// Definition for a binary tree node
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
private int maxDepth = -1;
private TreeNode lca;
public TreeNode lcaDeepestLeaves(TreeNode root) {
findLCA(root, 0);
return lca;
}
private int findLCA(TreeNode node, int depth) {
if (node == null) return depth;
int left = findLCA(node.left, depth + 1);
int right = findLCA(node.right, depth + 1);
int currentDepth = Math.max(left, right);
if (left == right && currentDepth >= maxDepth) {
lca = node;
maxDepth = currentDepth;
}
return currentDepth;
}
}解释
方法:
该题目的解决方案使用了深度优先搜索（DFS）来确定所有最深叶子节点的最近公共祖先。首先，使用一个递归函数 dfs，该函数对二叉树进行遍历，并返回每个节点的最大深度。在执行过程中，它同时更新全局变量 max_depth，用于记录树中叶子节点的最大深度。对于每个节点，如果左右子树返回的深度相等并且等于 max_depth，说明该节点是最深叶子节点的公共祖先。这种方式确保了只有当节点的所有子树深度都达到最大深度时，它才会被认为是公共祖先。
时间复杂度:
O(n)
空间复杂度:
O(h)，其中 h 是树的高度
代码细节讲解
🦆
递归函数dfs在访问到空节点时返回当前深度而不是-1的原因是什么？
▷🦆
在DFS的实现中，如何保证max_depth只记录最深的叶节点的深度，而不是任何节点的最大深度？
▷🦆
在判断节点是否为最深叶节点的公共祖先时，为什么需要左右子树的最大深度都等于max_depth？
▷🦆
如果左右子树的最大深度不相等，该如何更新当前节点的返回值？
▷