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

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int f=0;
    vector<int>v;
    void dfs(TreeNode* root,int n){
        if(f||!root)
            return ;
        if(root->val==n)
            f=1;
        v.push_back(root->val);
        dfs(root->left,n);
        dfs(root->right,n);
        if(!f){
            v.pop_back();
            return ;
        }
        return ;
    }
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        vector<int>v1;
        vector<int>v2;
        dfs(root,o1);
        v1=v;
        v.clear();
        f=0;
        dfs(root,o2);
        v2=v;
    //    return v1[1];
        map<int,int>m;
        for(int i=0;i<v1.size();i++){
            m[v1[i]]=1;
        }
    //    return m[1];
        reverse(v2.begin(),v2.end());
        for(int i=0;i<v2.size();i++){
            if(m[v2[i]])
                return v2[i];
        }
        return root->val;
    }
};