剑指Offer68-Ⅱ—二叉树的最近公共祖先

剑指Offer68-Ⅱ

本题与上一题的唯一不同就是上一题是二叉搜索树，本题是二叉树。

若 root 是 p, q 的 最近公共祖先 ，则只可能为以下情况之一：

1. p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
2. p = root ，且 q 在 root 的左或右子树中；
3. q=root ，且 p 在 root 的左或右子树中；

class Solution 
{
public:
    
    TreeNode* find_p_or_q(TreeNode* root,TreeNode* p,TreeNode* q)
    {
        if(root==nullptr || root==p || root==q)
        {
            //如果root为空，说明已经越过叶子节点了，还没找到p、q，就返回空就可以了
            //如果root就是p或者q，则已经找到p或者q了，返回之即可
            return root;
        }
        TreeNode* left_res = find_p_or_q(root->left,p,q); //去root的左子树去找p或者q
        TreeNode* right_res= find_p_or_q(root->right,p,q); //去root的右子树去找p或者q
        if(left_res!=nullptr&&right_res!=nullptr)
        {
            //如果在root的左右子树中都找到了p、q，说明root就是最近的公共祖先
            return root;
        }
        else if(left_res==nullptr&&right_res==nullptr)
        {
            //在左右子树中都没有找到p、q，说明以root为根的这颗树中就没有p和q
            return nullptr;
        }
        else if(left_res!=nullptr&&right_res==nullptr)
        {
            //root的右子树没有p、q，返回左子树的结果即可
            return left_res;
        }
        else
        {
            return right_res;
        }

    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 
    {
        return find_p_or_q(root,p,q);
    }
};