题解 | #利用二叉树后序遍历#

利用二叉树的后序遍历，当某一节点为输入值时，返回true，而当某一节点的左子节点或右子节点为true时，也返回true，当两者都为true时，则寻找到了最近公共根节点，需要注意的是，当两个节点互为父子关系时，所以需要改变一下返回条件。代码如下：

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int n;
    int f=0;
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        findr(root,o1,o2);
        return n;
    }

    bool findr(TreeNode* root,int o1,int o2)
    {
        if(root&&(!f))
        {
        bool n1=findr(root->left,o1,o2);
        bool n2=findr(root->right,o1,o2);
        if(root->val==o1||root->val==o2)
        {
            if(n1==true||n2==true)
            {
                n=root->val;
                f=1;
                return false;
            }
            return true;
        }
        if (n1==true&&n2==true)
        {
            n=root->val;
            f=1;
            return false;
        }
        else if(n1==true||n2==true)
        {
            return true;
        }
        else
        {
            return false;
        }
        }
        return false;
    }
};