【剑指Offer】7. 重建二叉树

骑猪看日落 2023-03-06 05:16 20阅读 0赞

[NowCode][]

## 题目描述 ##

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]

## 解题思路 ##

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。

import java.util.*;
    /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    public class Solution { 
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
            if(pre.length == 0 || in.length == 0)
                return null;
                
            TreeNode root = new TreeNode(pre[0]);
            for(int i = 0; i < in.length; i++) { 
                if(root.val == in[i]) { 
                    // 左子树
                    root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
                    //右子树
                    root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
                }
            }
            return root;
        }
    }

[NowCode]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&&tqId=11157&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzQ2OTY4MA_size_16_color_FFFFFF_t_70]: /images/20230208/e0bfd64c5e124eb5b536087f08b49a74.png

发表评论取消回复

表情：

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

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

相关阅读

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

[题目][Link 1] 思路： 1. 需要先将中序数组的【值-索引】信息进行储存，接着只要找到前序遍历的结点在中序遍历中的位置，就可以将中序数组分解为左右子树两部分；

我会带着你远行/ 2024年03月26日 13:52/ 0 赞/ 72 阅读

相关【剑指Offer】7. 重建二叉树

[NowCode][] 题目描述根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 ![在这里插入图片描

骑猪看日落/ 2023年03月06日 05:16/ 0 赞/ 21 阅读

相关剑指Offer-重建二叉树

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

我不是女神ヾ/ 2022年08月04日 12:49/ 0 赞/ 25 阅读

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

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

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

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

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

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

相关剑指offer：重建二叉树

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

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

相关剑指offer7:重建二叉树

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

墨蓝/ 2022年02月19日 09:07/ 0 赞/ 208 阅读

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

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

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

相关剑指offer 重建二叉树

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结

叁歲伎倆/ 2021年10月14日 03:40/ 0 赞/ 207 阅读

相关剑指offer：重建二叉树

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

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