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

题目描述
给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

示例1
输入
[3,5,1,6,2,0,8,#,#,7,4],5,1
返回值
3

解法

    // 解法: 递归(后序遍历框架)
    //  终止条件：1. 越过叶节点，直接返回null； 2. root == o1 || root == o2, 返回 root.
    //  递归： 分别获得左右子树上的最近公共祖先节点. 
    //        left=lowestCommonAncestor(root->left, o1, o2)
    //        right=lowestCommonAncestor(root->right, o1, o2)
    //  返回结果：根据左右子树结果，判断最终返回结果。
    //        1. left == null && right == null, return null  // o1, o2 不在root的两子树上
    //        2. left == null && right != null, return right // o1, o2 在root 右子树
    //        3. left != null && right == null, retut left  // o1, o2 在root 左子树
    //        4. left != null && right != null, return root // o1, o2 分别root的两子树上
    // 时间O（N）， 空间O（N）
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        if (root == nullptr) return INT_MIN;
        if (root->val == o1 || root->val == o2) return root->val;
        int left = lowestCommonAncestor(root->left, o1, o2);
        int right = lowestCommonAncestor(root->right, o1, o2);
        if (left == INT_MIN ) return right;
        if (right == INT_MIN) return left;
        return root->val;
    }