[剑指offer]重建二叉树

水深无声 2022-01-12 15:59 237阅读 0赞

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{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:
        vector<int> pre;
        vector<int> vin;
        TreeNode* recursive(int pl,int vl,int len)
        {
            if(0==len)return NULL;
            int root=pre[pl];
            TreeNode* node=new TreeNode(root);
            if(1==len)return node;
            
            int idx=0;
            for(idx=0;idx<len;idx++)
                if(vin[vl+idx]==root)break;
            
            
            node->left=recursive(pl+1,vl,idx);
            node->right=recursive(pl+idx+1,vl+idx+1,len-1-idx);
    
            return node;
        }
        TreeNode* reConstructBinaryTree(vector<int> pre_in,vector<int> vin_in) {
            pre=pre_in;
            vin=vin_in;
            return recursive(0,0,pre.size());
            
        }
        
    };

发表评论取消回复

表情：

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

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

相关阅读

相关【剑指offer】重建二叉树

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

朱雀/ 2022年06月16日 12:17/ 0 赞/ 193 阅读

相关剑指offer——重建二叉树

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

心已赠人/ 2022年05月31日 09:54/ 0 赞/ 199 阅读

相关《剑指offer》重建二叉树

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

喜欢ヅ旅行/ 2022年05月23日 04:29/ 0 赞/ 214 阅读

相关剑指offer：重建二叉树

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

左手的ㄟ右手/ 2022年04月14日 04:20/ 0 赞/ 237 阅读

相关剑指Offer-重建二叉树

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

蔚落/ 2022年03月02日 13:37/ 0 赞/ 267 阅读

相关 [剑指offer]重建二叉树

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

水深无声/ 2022年01月12日 15:59/ 0 赞/ 238 阅读

相关 [剑指offer]重建二叉树

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

叁歲伎倆/ 2021年12月05日 05:09/ 0 赞/ 318 阅读

相关【剑指offer】重建二叉树

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

深碍√TFBOYSˉ_/ 2021年11月09日 16:24/ 0 赞/ 299 阅读

相关剑指offer 重建二叉树

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

ゞ浴缸里的玫瑰/ 2021年10月13日 02:31/ 0 赞/ 332 阅读

相关剑指offer：重建二叉树

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

淡淡的烟草味﹌/ 2021年09月16日 06:38/ 0 赞/ 334 阅读