题解 | #输出二叉树的右视图#

输出二叉树的右视图

http://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0

先递归建树,然后再层次遍历,每次取每层中最右边的数

public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    TreeNode* construct(vector<int> pre,int l1,int r1,vector<int> mid,int l2,int r2){
        if(l1>r1||l2>r2) return NULL;
        TreeNode* root=new TreeNode(pre[l1]);
        int index=l2;
        for(index;index<=r2;index++){
            if(mid[index]==pre[l1]) break;
        }
        root->left=construct(pre,l1+1,l1+index-l2,mid,l2,index-1);
        root->right=construct(pre,l1+index-l2+1,r1,mid,index+1,r2);
        return root;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        TreeNode* root=construct(xianxu,0,xianxu.size()-1,zhongxu,0,zhongxu.size()-1);
        vector<int> res;
        if(root==NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int size=q.size();
            bool flag=true;
            while(size--){
                TreeNode* node=q.front();
                q.pop();
                if(flag){
                    res.push_back(node->val);
                    flag=false;
                }
                if(node->right) q.push(node->right);
                if(node->left) q.push(node->left);
            }
                       
        }
        return res;
    }
};
全部评论

相关推荐

05-29 22:11
门头沟学院 Java
Elastic90:抛开学历造假不谈,这公司的招聘需求也挺怪的,Java开发还要求你有图文识别、移动端开发和c++的经验,有点逆天了。
点赞 评论 收藏
分享
人力小鱼姐:实习经历没有什么含金量,咖啡店员迎宾这种就别写了,其他两段包装一下 想找人力相关的话,总结一下个人优势,结合校园经历里有相关性的部分,加一段自我评价
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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