二叉树公共组先,剑指Offer

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

http://www.nowcoder.com/questionTerminal/e0cc33a83afe4530bcec46eba3325116

class Solution {
public:
    //先找到 路径,从根节点出发
    bool getPath(TreeNode* root,list<TreeNode*>& path,int value){
        path.push_back(root);
        bool found=false;;
        if(root->val==value){
            found=true;
            return true;
        } 
        if(root->left)
            found=getPath(root->left,path,value);
        if(root->right)
            found= found ||getPath(root->right,path,value);

        if(!found)
            path.pop_back();
        return found;
    }
    //两条路径的最后一个公共结点就是组先
    int commonNode(const list<TreeNode*>&path1,const list<TreeNode*>&path2){
        list<TreeNode*>::const_iterator iter1=path1.begin();
        list<TreeNode*>::const_iterator iter2=path2.begin();

        TreeNode* pLast=nullptr;
        while(iter1!=path1.end() && iter2!=path2.end()){
            if(*iter1==*iter2)
                pLast=(*iter1);

            ++iter1;
            ++iter2;
        }
        return pLast->val;
    }
    //二叉树公共组先
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {

        list<TreeNode*> path1;
        getPath(root,path1,o1);

        list<TreeNode*> path2;
        getPath(root,path2,o2);

        return commonNode(path1,path2);

    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:46
暑期就挂了,秋招还有机会吗
大聪明777:研发提前批,14号刚开的,官网上面的配图上有写。提前批没过的话,秋招还可以投,不过前面的笔试/面试记录会被保留,供秋招参考
26届校招投递进展
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务