重建二叉树

阳光穿透心脏的1/2处 2022-03-11 20:44 202阅读 0赞

时间限制：1秒 空间限制：32768K 热度指数：524408  
算法知识视频讲解  
题目描述  
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    int i,j;
        vector<int> pre1,pre2,vin1,vin2;
        if(pre.size()==0)
            return NULL;
        struct TreeNode *head=new TreeNode(pre[0]);
        for(i=0;i<vin.size();i++){
            if(pre[0]==vin[i]){
                break;
            }
            vin1.push_back(vin[i]);
        }
        for(j=i+1;j<vin.size();j++){
            vin2.push_back(vin[j]);
        }
        for(j=1;j<i+1;j++)
        {
            pre1.push_back(pre[j]);
        }
        for(j=i+1;j<pre.size();j++)
        {
            pre2.push_back(pre[j]);
        }
        head->left=reConstructBinaryTree(pre1,vin1);
        head->right=reConstructBinaryTree(pre2,vin2);
        return head;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关重建二叉树

![这里写图片描述][70] class TreeNode { int val; TreeNode left; Tre

ゝ一世哀愁。/ 2022年05月26日 07:57/ 0 赞/ 198 阅读

相关重建二叉树

二叉树重建根据二叉树的前序遍历和中序遍历，重建二叉树。综合利用前序遍历和中序遍历的特点。 / 题目描述输入某二叉树的前序遍历和中序遍历的

Love The Way You Lie/ 2022年05月14日 15:48/ 0 赞/ 230 阅读

相关重建二叉树

重建二叉树输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。如前序\{1,2,4,7,3,5,6,8

亦凉/ 2022年04月24日 13:54/ 0 赞/ 202 阅读

相关重建二叉树

/ Definition for binary tree struct TreeNode { int val;

灰太狼/ 2022年04月03日 13:44/ 0 赞/ 257 阅读

相关重建二叉树

[重建二叉树][Link 1] 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前

偏执的太偏执、/ 2022年03月25日 15:18/ 0 赞/ 160 阅读

相关重建二叉树

时间限制：1秒空间限制：32768K 热度指数：524408 算法知识视频讲解题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序

阳光穿透心脏的1/2处/ 2022年03月11日 20:44/ 0 赞/ 203 阅读

相关重建二叉树

题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6

古城微笑少年丶/ 2022年03月06日 12:26/ 0 赞/ 245 阅读

相关二叉树重建

给定二叉树的先序遍历序列和中序遍历序列，进行二叉树的重建以及后序遍历队列。突然看到这个问题。。发现之前的想法都忘记了=\_=||，果然算法题一日不写手生啊，还是得好好坚持

淡淡的烟草味﹌/ 2021年12月14日 04:15/ 0 赞/ 293 阅读

相关重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序

末蓝、/ 2021年11月16日 15:14/ 0 赞/ 264 阅读

相关重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序

妖狐艹你老母/ 2021年09月23日 09:20/ 0 赞/ 384 阅读