236. 二叉树的最近公共祖先
一句话套路后序:两侧都有即答案,否则返回非空那侧
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出:3 解释:节点5和节点1的最近公共祖先是节点3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出:5 解释:节点5和节点4的最近公共祖先是节点5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2 输出:1
提示:
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
思路
时间
O(n)空间
O(h)思路
返回值语义(背下来,一类题全通):
- · 本结点为 null 或等于 p/q -> 直接返回本结点
- · 左右都返回非空 -> p、q 分居两侧,本结点就是 LCA
- · 只有一侧非空 -> 把那一侧的结果原样上传
注意
这题不是 BST!不能靠大小比较剪枝(那是 Q235)。
图解
二叉树(来自本仓库测试数据,
nullopt 表示空位)C++17 题解
namespace lc0236 {
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root; // 分叉点
return left ? left : right;
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0236::Solution s;
TreeNode* t = buildTree({3, 5, 1, 6, 2, 0, 8, nullopt, nullopt, 7, 4});
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 5), findNode(t, 1)), findNode(t, 3));
// p 是 q 的祖先时,LCA 就是 p 本身(本题允许这种输入)
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 5), findNode(t, 4)), findNode(t, 5));
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 7), findNode(t, 6)), findNode(t, 5));
CHECK_EQ(s.lowestCommonAncestor(t, findNode(t, 0), findNode(t, 8)), findNode(t, 1));
freeTree(t);