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

我的思路是用了一个贪心和动态规划（可能吧）的思想，每次找一个节点都是需要遍历才知道会不会是其子树有没有这个键值的节点，而只要子树的键值有这个点，那么该节点及其的祖先节点的子树都有这个节点，我们不如记录下来哪些节点的子树有这个节点，而第一个键值出现的节点就是离该值节点最近的节点和最有可能的节点（贪心），其父亲节点也会是其可能节点。我们只需遍历两次子树就可以记录所有可能的节点，时间复杂度O(n)、空间复杂度O(n)。最近的最先记录入数组，因此从前往后遍历数组就可以。

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */

    bool exist(TreeNode* root, int o1,vector<TreeNode*> &target){
        if(root){
            if(exist(root->left,o1,target)){
                target.push_back(root);
                return true;
            }
            if(exist(root->right,o1,target)){
                target.push_back(root);
                return true;
            }
            if(root->val==o1){
                target.push_back(root);
                return true;
            }

        }
        return false;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<TreeNode*> target; 
        vector<TreeNode*> target2; 
        exist(root,o1,target);
        exist(root,o2,target2);
        map<TreeNode*,int> hash;
        for(int i=0;i<target.size();i++){
            hash[target[i]]++;
        }
        int i;
        for(i=0;i<target2.size()&&!hash[target2[i]];i++){
            hash[target2[i]]++;
        }
        return target2[i]->val;
        return NULL;

    }
};