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

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

引用

CSDN

1.

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

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

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

示例

输入：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 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

• 树中节点数目在范围 [2, 105] 内。
• -10^9 <= Node.val <= 10^9
• 所有 Node.val 互不相同 。
• p != q
• 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);
    }
}

方法二：路径查找

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

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();
}