二叉树的最近公共祖先

初阶牛

发布于 2023-10-14 09:29:03

22700

代码可运行

运行总次数：0

代码可运行

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中) 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:记录力扣题二叉树的最近公共祖先. 金句分享: ✨生活本就沉默,但是跑起来有风!✨

题目介绍:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

解题思路

幻想: 如果该树是三叉树就好了,有一个指向父亲的指针,那样就可以转化为两个链表相交,求交点,只需要快慢指针就行了.

正经解题:

试着观察最近公共祖先,如果只是普通的祖先,则这两个结点都在其中的一个子树中. (1)全在该结点的左子树 (2)全在该结点的右子树
如果是最近的公共祖先,则一个结点在左子树,一个在右子树.
(1) 如果全在左子树,则往左子树方向继续找. (2) 如果全在右子树,同理;
特殊情况,其中一个是另一个的祖先(父亲),直接返回该结点(祖先)即可.

代码实现:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==p||root==q)	//其中一个是另一个的祖先
        {
            return root;
        }
        
        //判断在不在左子树
        bool left_p=find(root->left,p);
        bool left_q=find(root->left,q);
		
		//判断在不在右子树
        bool right_p=!left_p;
        bool right_q=!left_q;
	
		
        if(left_p && left_q)
        {
        	//如果全在左子树,则往左子树继续遍历
            root=lowestCommonAncestor( root->left,p,q);
        }
        else if(right_p && right_q)
        {
        	//如果全在右子树,则往右子树继续遍历
            root=lowestCommonAncestor( root->right,p,q);
        }
        return root;
    }
    bool find(TreeNode* root,TreeNode* node)
    {
        if(root==nullptr) return false;
        if(root==node)
        {
            return true;
        }
        return find(root->left,node)||find(root->right,node);
    }
};