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

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

class Solution {
private:
        unordered_map<int, TreeNode*>ret;
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int>path;
        dfs(root);
        ret[root->val]=nullptr;
        TreeNode*oo1=ret[o1];
        TreeNode*oo2=ret[o2];
        path.emplace_back(o1);
        while(oo1){
            path.emplace_back(oo1->val);
            oo1=ret[oo1->val];
        }
        while(oo2){
            if(find(path.begin(),path.end(),o2)!=path.end())return o2;
            if(find(path.begin(),path.end(),oo2->val)!=path.end())return oo2->val;
            oo2=ret[oo2->val];
        }
        return -1;
    }
    
    void dfs(TreeNode*root){
        if(root->left){
            ret[root->left->val]=root;
            dfs(root->left);
        }
        if(root->right){
            ret[root->right->val]=root;
            dfs(root->right);
        }
    }
    
};