题目
- 给出一个二叉树,输入两个树节点,求它们的最低公共祖先。
- 一个树节点的祖先节点包括它本身。
注意
:
输入的二叉树不为空;
输入的两个节点一定不为空,且是二叉树中的节点;
- 数据范围
树中节点数量:$0 ≤ n ≤ 500$。
示例
- 二叉树$[8, 12, 2, null, null, 6, 4, null, null, null, null]$如下图所示:
8
/ \
12 2
/ \
6 4
- 如果输入的树节点为
2
和12
,则输出的最低公共祖先为树节点8
。 - 如果输入的树节点为
2
和6
,则输出的最低公共祖先为树节点2
。
代码
- $O(n)$【视频讲解】
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root)
return NULL;
if(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;
if(left) return left;
else return right;
} };
代码分析
:递归还是不太好理解啊。
本文题目
:树中两个结点的最低公共祖先