剑指--找出两个二叉树节点的最小父节点

方法1：

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    void push_vec(TreeNode* root, int o1, 
                  vector<int>& path1, 
                  bool& find1) {
        if (root == nullptr || (find1)) {
            return;
        }
        if (!find1 && root->val == o1) {
            path1.push_back(root->val);
            find1 = true;
            return;
        }
             
        if (!find1 && root->left) {
            path1.push_back(root->val);
            push_vec(root->left, o1, path1, find1);
            if(!find1) {
                path1.pop_back();
            }
        }
         if (!find1 && root->right) {
            path1.push_back(root->val);
            push_vec(root->right, o1, path1, find1);
            if(!find1) {
                path1.pop_back();
            }
        }
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        bool find1 = false;
        bool find2 = false;
        vector<int> path1;
        vector<int> path2;
        push_vec(root, o1, path1, find1);
        push_vec(root, o2, path2, find2);
        int i,j;
        for (i = 0, j = 0; i < path1.size() && j < path2.size();
            i++, j++) {
            if (path1[i] != path2[j])
                break;
        }
        return path1[i-1];
    }
};

时间复杂度2O(n)和空间复杂度2O(n)都高，

方法2

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    TreeNode* find(TreeNode* root, int o1, int o2) {
        if (!root || root->val == o1 || root->val == o2) {
            return root;
        }
        TreeNode* left = find(root->left, o1, o2);
        if (left == nullptr) {
            return find(root->right, o1, o2);
        }
        TreeNode* right = find(root->right, o1, o2);
        if (right == nullptr) {
            return left;
        }
        return root;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        return find(root, o1, o2)->val;
    }
};