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

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

递归写法

classSolution{public:/**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    
    TreeNode*find(TreeNode*root,int o1,int o2){if(root==NULL)returnNULL;if(root->val==o1||root->val==o2)return root;
        
        TreeNode*left=find(root->left,o1,o2);
        
        TreeNode*right=find(root->right,o1,o2);if(left&&right)return root;elseif(left==NULL)return right;elsereturn left;}intlowestCommonAncestor(TreeNode* root,int o1,int o2){// write code here
        
        TreeNode*t=find(root,o1,o2);if(t)return t->val;elsereturn-1;}};

非递归写法

classSolution{public:
    
    map<int,int>mp;voiddfs(TreeNode*root,TreeNode*father){

        mp[root->val]=father->val;if(root->left)dfs(root->left,root);if(root->right)dfs(root->right,root);}intlowestCommonAncestor(TreeNode* root,int o1,int o2){if(root==NULL)returnNULL;
        
        TreeNode*zu=newTreeNode(-1000000);dfs(root,zu);
        
        map<int,int> mp1;while(o1!=-1000000){
            mp1[o1]=1;
            o1=mp[o1];}while(o2!=-1000000){if(mp1[o2])return o2;
            
            o2=mp[o2];}return0;}};