二叉树公共组先,剑指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);

    }
};
全部评论

相关推荐

湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
07-07 12:25
门头沟学院 Java
程序员牛肉:你这个智邮公司做的就是那个乐山市税务系统的服务吗?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:35
程序员小白条:话太多,没实力和学历,差不多回答回答就行了,身份地位不一样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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