力扣：236.二叉树的最近公共祖先(C++)

文章目录

1. 题目描述
2. 题目解析
- 2.1 思路一
- 2.1 思路二

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
题目来源: 力扣…二叉树的最近公共祖先

1. 题目描述

百度百科中最近公共祖先的定义为：“对于有根树 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 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

树中节点数目在范围 [2, 105] 内。
-10^9 <= Node.val <= 10^9
所有 Node.val 互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

2. 题目解析

2.1 思路一

判断p q是否分别在当前节点左右子树中或者其中一个就是树的根。
我们可以通过递归来实现这个过程。具体思想是：

如果当前节点是其中一个目标节点，则直接返回当前节点。
如果在当前节点的左右子树中分别找到目标节点，说明当前节点就是最近公共祖先。
否则 p q都在当前节点的左子树或者右子树中，因此在左子树和右子树中继续递归查找。

代码如下：

//判断节点x是否在树中
bool InTree(TreeNode* root, TreeNode* x)
{
    if (root == nullptr) return false;
    if (root == x) return true;
    return InTree(root->left, x) || InTree(root->right, x);
}
reeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
{
	//当前节点是其中一个目标节点，则直接返回当前节点
    if (root == p || root == q) return root;
    //去当前左子树中查找p节点
    bool pInLeft = InTree(root->left, p);
    //在左子树中就不在右子树，因此对pInLeft取反，就是其是否在右子树中的情况
    bool pInRight = !pInLeft;
    //对q节点和对p节点一样
    bool qInLeft = InTree(root->left, q);
    bool qInRight = !qInLeft;
	//在当前节点的左右子树中分别找到目标节点，说明当前节点就是最近公共祖先
    if ((pInLeft && qInRight) || (qInLeft && pInRight))
    {
    	return root;
    } 
    else if (pInLeft && qInLeft)
    {
    	//p q都在当前节点的左子树中，因此在左子树中继续递归查找
    	return lowestCommonAncestor(root->left, p, q);
    } 
    else 
    {
    	//p q都在当前节点的右子树中，因此在右子树中继续递归查找
    	return lowestCommonAncestor(root->right, p, q);
    }
}

2.1 思路二

通过找到从根节点到目标节点的路径，然后将其转换成链表相交问题。
这种方法的步骤如下：

找到根节点到p节点的路径。
找到根节点到q节点的路径。
找到这两条路径的最后一个公共节点。

画个图理解一下：

在这里插入图片描述
代码如下：

//找根节点到节点x的路径
 bool GetPath(TreeNode* root, TreeNode* x, stack<TreeNode*>& st)
    {
        if (root == nullptr) return false;
        st.push(root);
        if (root == x) return true;
        if (GetPath(root->left, x, st))
        {
            return true;
        }
        if (GetPath(root->right, x, st))
        {
            return true;
        }
        st.pop();
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        stack<TreeNode*> pPath, qPath;
        GetPath(root, p, pPath);//找到根节点到p节点的路径。
        GetPath(root, q, qPath);//找到根节点到q节点的路径。
        //路径长的先走，直到路径一样长
        while (pPath.size() != qPath.size())
        {
            if (pPath.size() > qPath.size())
            {
                pPath.pop();
            }
            else
            {
                qPath.pop();
            }
        }
        //找这两条路径的最后一个公共节点
        while (pPath.top() != qPath.top())
        {
            pPath.pop();
            qPath.pop();
        }
        return pPath.top();
    }