题解 | #重建二叉树#

重建二叉树

http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        if(pre.size()==0 || vin.size()==0)    return nullptr;

        // 找到根节点的值,并构建根节点
        int rootval = pre[0];
        TreeNode* root = new TreeNode(rootval);

        // 找到根节点在中序数组中的位置,可以标志左右子树的节点各有多少个
        int index=0;
        for(; index<vin.size(); index++) {
            if(vin[index] == rootval) {
                break;
            }
        }
        // 切割数组 vin
        vector<int> vinleft(vin.begin(), vin.begin()+index);
        vector<int> vinright(vin.begin()+index+1, vin.end());
        // 切割数组 pre
        vector<int> preleft(pre.begin()+1, pre.begin()+1+index);
        vector<int> preright(pre.begin()+1+index, pre.end());

        // 递归生成左右子树
        root->left = reConstructBinaryTree(preleft, vinleft);
        root->right = reConstructBinaryTree(preright, vinright);

        // 返回根节点
        return root;
    }
};
全部评论

相关推荐

07-03 16:02
门头沟学院 Java
今天面试,非常紧张,面试官问我springboot有哪些核心模块都答不上来了,真的对自己无语了!
程序员小白条:28届我勒个去,很多人面试都没机会
查看1道真题和解析
点赞 评论 收藏
分享
白火同学:能。我当初应届沟通了1200,收简历50,面试10左右吧,加油投吧
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

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