题解 | #重建二叉树#

重建二叉树

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 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

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