题解 | #在二叉树中找到两个节点的最近公共祖先#

众所周知：
（1）二叉搜索树只要找到当前节点val位于两个结点val之间，就是最低公共父节点。
（2）带parent结点的二叉树，可以先遍历到结点位置，反向根据parent找到root建立两个链表，求两个链表的公共结点。
（3）没有parent的普通二叉树。需要使用后序遍历，并且是从左到右的顺序遍历。
如果从左子树遍历到结点，则用left记录。
如果从右子树遍历到结点，则用right记录。
TreeNode* lowestCommonAncestorCore(TreeNode* root,int o1, int o2)

{

    if(root == nullptr)
        return nullptr;

    if(root->val == o1 || root->val == o2 )
    return root;

    TreeNode* left = nullptr;
    TreeNode* right= nullptr;
    if(root->left != nullptr)
        left =  lowestCommonAncestorCore(root->left,o1,o2);
    if(root->right != nullptr)
        right = lowestCommonAncestorCore(root->right,o1,o2);

    if(left && right)
        return root;
    else
        return left?left:right;
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
    // write code here
    return(lowestCommonAncestorCore(root,o1,o2)->val);

}