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

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

引用

CSDN

1.

https://blog.csdn.net/m0_50655389/article/details/139233784

在算法面试和编程练习中，二叉树的最近公共祖先问题是一个经典且重要的题目。本文将详细讲解如何使用C++语言解决这个问题，通过两种不同的思路和代码实现，帮助读者深入理解这一算法问题。

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, 10^5] 内。
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

2. 题目解析

2.1 思路一

判断p q是否分别在当前节点左右子树中或者其中一个就是树的根。

我们可以通过递归来实现这个过程。具体思想是：

1. 如果当前节点是其中一个目标节点，则直接返回当前节点。
2. 如果在当前节点的左右子树中分别找到目标节点，说明当前节点就是最近公共祖先。
3. 否则 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);
}
TreeNode* 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 思路二

通过找到从根节点到目标节点的路径，然后将其转换成链表相交问题。

这种方法的步骤如下：

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

画个图理解一下：

代码如下：

//找根节点到节点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();
}