85 lines
2.8 KiB
Markdown
85 lines
2.8 KiB
Markdown
|
# 毎日一题 - 1123.最深叶节点的最近公共祖先
|
|||
|
|
|
|||
|
|
## 信息卡片
|
|||
|
|
|
|||
|
|
* 时间：2019-08-08
|
|||
|
|
* 题目链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/
|
|||
|
|
- tag：`DFS` `Tree`
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
给你一个有根节点的二叉树，找到它最深的叶节点的最近公共祖先。
|
|||
|
|
|
|||
|
|
回想一下：
|
|||
|
|
|
|||
|
|
* 叶节点是二叉树中没有子节点的节点
|
|||
|
|
* 树的根节点的深度为0，如果某一节点的深度为d，那它的子节点的深度就是d+1
|
|||
|
|
* 如果我们假定A是一组节点S的最近公共祖先，```<font color="#c7254e" face="Menlo, Monaco, Consolas, Courier New, monospace">S</font>```中的每个节点都在以 A 为根节点的子树中，且 A的深度达到此条件下可能的最大值。
|
|||
|
|
|
|||
|
|
|
|||
|
|
**示例 1：**
|
|||
|
|
```
|
|||
|
|
输入：root = [1,2,3]
|
|||
|
|
输出：[1,2,3]
|
|||
|
|
```
|
|||
|
|
**示例 2：**
|
|||
|
|
```
|
|||
|
|
输入：root = [1,2,3,4]
|
|||
|
|
输出：[4]
|
|||
|
|
```
|
|||
|
|
**示例 3：**
|
|||
|
|
```
|
|||
|
|
输入：root = [1,2,3,4,5]
|
|||
|
|
输出：[2,4,5]
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
提示：
|
|||
|
|
* 给你的树中将有1 到 1000 个节点。
|
|||
|
|
* 树中每个节点的值都在 1 到 1000 之间。
|
|||
|
|
## 参考答案
|
|||
|
|
深度优先搜索
|
|||
|
|
>
|
|||
|
|
先来解释一下题目意思，给你一个树根，返回最深叶节点的最近公共祖先，存在以下俩种情况：
|
|||
|
|
* 最深叶节点只有一个，那么这个叶节点本身就是它的最近公共祖先
|
|||
|
|
* 最深叶节点不止一个，那就不断深搜找到最大深度，然后回溯，出递归栈时最后一个左右子树等高的节点就是该树的最深节点的最近祖先
|
|||
|
|
>
|
|||
|
|
所以代码思路分俩条路:只有一个最深叶节点找到并更新返回值;存在多个最深叶节点，找到最后一个子节点等高的节点更新返回值。后者的存在可以被证明，所以后者可以更改前者的结果。
|
|||
|
|
```c++
|
|||
|
|
class Solution {
|
|||
|
|
private:
|
|||
|
|
TreeNode *ans;
|
|||
|
|
int max_deep;
|
|||
|
|
int DFS(TreeNode *root, int nums){
|
|||
|
|
//叶子节点
|
|||
|
|
if(root->left == NULL && root->right == NULL){
|
|||
|
|
//更新最大深度，记录最大深度的叶节点
|
|||
|
|
if(nums>max_deep){
|
|||
|
|
ans = root;
|
|||
|
|
max_deep = nums;
|
|||
|
|
}
|
|||
|
|
return nums;
|
|||
|
|
}
|
|||
|
|
int num_l=0, num_r=0;
|
|||
|
|
//递归左右子树
|
|||
|
|
if(root->left) num_l = DFS(root->left, nums+1);
|
|||
|
|
if(root->right) num_r = DFS(root->right, nums+1);
|
|||
|
|
//存储多个最深叶节点，递归出最近公共祖先
|
|||
|
|
if(num_l == num_r && num_l>=max_deep){
|
|||
|
|
ans = root;
|
|||
|
|
max_deep = num_l;
|
|||
|
|
}
|
|||
|
|
//返回最大深度
|
|||
|
|
return max(num_l, num_r);
|
|||
|
|
}
|
|||
|
|
public:
|
|||
|
|
TreeNode* lcaDeepestLeaves(TreeNode* root) {
|
|||
|
|
//初始化根、最大深度
|
|||
|
|
ans = root;
|
|||
|
|
max_deep = INT_MIN;
|
|||
|
|
int deep_n = DFS(root, 1);
|
|||
|
|
return ans;
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
```
|
|||
|
|
## 其他优秀解答
|
|||
|
|
|
|||
|
|
> 暂缺
|