题目描述
给定一个有根结点的二叉树,找到它最深的叶结点的最近公共祖先。
回想一下:
- 叶结点 是二叉树中没有子结点的结点。
- 树的根结点的 深度 为 0,如果某一结点的深度为
d
,那它的子结点的深度就是d+1
。 - 一组结点
S
的 最近公共祖先 是有最大深度的结点A
,使得S
中的每个结点都在以A
为根的子树中。
样例
输入:root = [1,2,3]
输出:[1,2,3]
解释:
The deepest leaves are the nodes with values 2 and 3.
最深的叶结点是值为 2 和 3 的结点。
这些叶结点的最低公共祖先是值为 1 的结点。
返回的答案是一个 TreeNode 对象(不是一个数组)的序列化表示 "[1,2,3]"。
输入:root = [1,2,3,4]
输出:[4]
输入:root = [1,2,3,4,5]
输出:[2,4,5]
限制
- 给定的树中将有 1 到 1000 个结点。
- 树中结点的值互不相同,且在 1 到 1000 之间。
算法
(递归) $O(n)$
- 从根结点开始递归,每次递归返回一个数对,表示当前以
rt
为根的子树时,答案结点的指针和最深叶结点的深度。 - 如果
rt
为空,则返回空指针且深度为 0。否则,比较左右子树的两个返回值。 - 若左子树的最大深度和右子树的最大深度相等,则说明答案需要更新为当前结点
rt
,所以返回(rt, l.second + 1)
。 - 若左子树的最大深度大于右子树,则返回
(l.first, l.second + 1)
;否则返回(r.first, r.second + 1)
。 - 最后答案就是
solve(root).first
。
时间复杂度
- 每个结点仅遍历一次,故时间复杂度为 $O(n)$。
空间复杂度
- 由于使用了递归,所以需要系统栈空间,假设树的最大高度为 $h$,则空间复杂度为 $O(h)$。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
pair<TreeNode*, int> solve(TreeNode *rt) {
if (rt == nullptr)
return make_pair(nullptr, 0);
auto l = solve(rt -> left);
auto r = solve(rt -> right);
if (l.second == r.second) {
return make_pair(rt, l.second + 1);
} else if(l.second > r.second) {
return make_pair(l.first, l.second + 1);
} else {
return make_pair(r.first, r.second + 1);
}
}
TreeNode* lcaDeepestLeaves(TreeNode* root) {
return solve(root).first;
}
};