剑指offer | 07.重建二叉树

￡神魔★判官ぃ 2022-12-21 14:55 142阅读 0赞

**题目内容**

> 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
> 
> 例如，给出
> 
> 前序遍历 preorder = \[3,9,20,15,7\]  
> 中序遍历 inorder = \[9,3,15,20,7\]
> 
> 返回如下的二叉树：

3
       / \
      9  20
        /  \
       15   7

> 限制：0 <= 节点个数 <= 5000

--------------------

**思路**

*  前序遍历：根左右
 *  中序遍历：左根右
 *  所以我们知道谦虚遍历第一个数是根，再去中序遍历中找到根，从而划分出左右子树，再通过递归把下面的左右子树都构建出来。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution { 
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 
            //递归分治
            return recursionBuild(preorder.begin(),preorder.end(),inorder.begin(),inorder.end());
        }
    
        //递归分治
        TreeNode* recursionBuild(vector<int>::iterator preBegin, vector<int>::iterator preEnd,vector<int>::iterator inBegin, vector<int>::iterator inEnd )
        { 
            if(inEnd==inBegin) return NULL;
            TreeNode* cur = new TreeNode(*preBegin);
            auto root = find(inBegin,inEnd,*preBegin);
            cur->left = recursionBuild(preBegin+1,preBegin+1+(root-inBegin),inBegin,root);
            cur->right = recursionBuild(preBegin+1+(root-inBegin),preEnd,root+1,inEnd);
            return cur;
        }
    };

![在这里插入图片描述][20201116183627309.png_pic_center]

[20201116183627309.png_pic_center]: /images/20221120/318b37044eaf4b7e8ecfe389549a6232.png

发表评论取消回复

表情：

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

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

相关阅读

相关剑指 Offer 07. 重建二叉树

今天通过这道题来研究研究前序遍历，中序遍历之间到底有什么关系题目描述： > 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。 > 假设输入的前

迈不过友情╰/ 2023年10月11日 17:28/ 0 赞/ 19 阅读

相关剑指 Offer 07-重建二叉树

题目 ![92242daf9bfddc7239797dc34703a6c1.png][] 事先给定的代码 public class TreeNode

电玩女神/ 2023年09月27日 07:26/ 0 赞/ 16 阅读

相关剑指 Offer 07. 重建二叉树

题目来源 [剑指 Offer 07. 重建二叉树][Offer 07.] 类似的题目 [106. 从中序与后序遍历序列构造二叉树][106.] 题目描述 !

水深无声/ 2022年12月22日 11:10/ 0 赞/ 127 阅读

相关剑指offer | 07.重建二叉树

题目内容 > 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 > > 例如，给出 > > 前序遍历 pre

￡神魔★判官ぃ/ 2022年12月21日 14:55/ 0 赞/ 143 阅读

相关剑指 Offer 07. 重建二叉树

题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出 > 前序遍历 preorder =

左手的ㄟ右手/ 2022年12月16日 11:57/ 0 赞/ 193 阅读

相关剑指 Offer 07. 重建二叉树

题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出前序遍历 preorder = \[3

╰半橙微兮°/ 2022年12月07日 12:16/ 0 赞/ 119 阅读

相关剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出前序遍历 preorder = \[3,9,20

骑猪看日落/ 2022年10月16日 10:00/ 0 赞/ 127 阅读

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

重建二叉树问题描述：前序中序构建二叉树 [剑指 Offer 07. 重建二叉树][Offer 07.] [105. 从前序与中序遍历序列构造二叉树][105.]

缺乏、安全感/ 2022年10月08日 11:12/ 0 赞/ 141 阅读

相关剑指 Offer 07. 重建二叉树

链接：[https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/][https_leetcode-cn.com_

爱被打了一巴掌/ 2022年10月06日 14:52/ 0 赞/ 136 阅读

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

[面试题07. 重建二叉树][07.] 难度中等72 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

心已赠人/ 2021年10月03日 02:24/ 0 赞/ 290 阅读