letcode::二叉树的最近公共祖先
题目描述:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/b456a72f3e61434392c6c0b646bac724.png#pic_center = 800x)
思路:
从root节点开始,判断p、q节点是在左子树还是右子树。
- 如果p、q节点都在左子树,则继续往左递归(注意p、q节点本事就是公共祖先的情况)
- 如果p、q节点都在右子树,则继续往右递归
- 如果p、q节点一个在左子树,一个在右子树,则说明当前的root节点是最近公共祖先
代码:
class Solution {
public:
bool Find(TreeNode* tree, TreeNode* x)
{
if (tree == nullptr)
{
return false;
}
return tree == x || Find(tree->left, x) || Find(tree->right, x);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr)
{
return nullptr;
}
if (root == p || root == q)
{
return root;
}
bool pInLeft, pInRight, qInLeft, qInRight;
pInLeft = Find(root->left, p);
pInRight = !pInLeft;
qInLeft = Find(root->left, q);
qInRight = !qInLeft;
if (pInLeft && qInLeft)
{
return lowestCommonAncestor(root->left, p, q);
}
else if (pInRight && qInRight)
{
return lowestCommonAncestor(root->right, p, q);
}
else
{
return root;
}
}
};
原文地址:https://blog.csdn.net/Raymood_/article/details/136967404
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!