剑指offer【7】：重建二叉树

?xiaoxiao, 发布于2019-08-16 18:41 / 1894人阅读

摘要：例如，输入前序遍历序列和中序遍历序列，则重建二叉树并返回。题解对二叉树前序中序遍历的考察，采用递归的方法解决问题，难点是确定每一个子树的临界点。

题目

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

题解

对二叉树前序、中序遍历的考察，采用递归的方法解决问题，难点是确定每一个子树的临界点。

public class Solution {
    private Map map = new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        
        for(int i = 0; i< in.length; i++){
            map.put(in[i], i);
        }
        
        return reConstructBinaryTree(pre, 0, pre.length-1,0);
        
    }
    
    public TreeNode reConstructBinaryTree(int [] pre, int preL, int preR, int inL){
        //【易错点】=不可以写，等于说明存在一个节点
        if(preL > preR){
            return null;
        }
        TreeNode root = new TreeNode(pre[preL]);
        int index = map.get(pre[preL]);
        int k = index - inL;
        root.left = reConstructBinaryTree(pre, preL+1, preL+k, inL);
        root.right = reConstructBinaryTree(pre, preL+k+1, preR, index+1);
        return root;
    }
    
    
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int x) { val = x; }
}

注意点

    if(preL > preR){
        return null;
    }

这里判断条件不能有等于，等于相当于该子树只有一个节点

云服务器 GPU云服务器二叉树 python二叉树平衡二叉树实现二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75565.html

【剑指offer】4.二叉树的遍历和重建

摘要：第一行为前序遍历，第二行为中序遍历。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。根据前序遍历和中序遍历的结果可以拿到左子中序遍历和右侧为右子树中序遍历左子树的前序遍历和右子树的前序遍历然后递归左子树和右子树的完成重建。二叉树简介基本结构： function TreeNode(x) { this.val = x; this.left = null; ...

zhangyucha0 2019-08-23 14:40 评论0 收藏0
#yyds干货盘点#剑指 Offer 07. 重建二叉树

摘要：题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。例如，给出前序遍历中序遍历返回如下的二叉树限制节点个数答案要使用这个方法，首先要将一个原始的数组，从下标开始复制，复制到上标不包括，生成一个新的数组。题目输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不...

paney129 2021-11-24 09:39 评论0 收藏0
剑指Offer---根据前序遍历和中序遍历重建二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。代表前序数组，代表中序数组。中序遍历的左右子树比较好找，但是前序遍历的左右子树想到比较难找。 jdk 版本： jdk 1.8 题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,...

tainzhi 2019-08-16 10:53 评论0 收藏0
PHPer面试必看：分门别类带你撸《剑指Offer》之二叉树

摘要：例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。操作给定的二叉树，将其变换为源二叉树的镜像。剑指中还有一道类似的变种题目，就是下面的这道，之字形遍历二叉树。最后下面的两道题目分别运用了二叉树先序中序遍历算法。开篇以下内容可能偏应试但很好理解，所以大家一定要坚持看下去，因为我们变强的过程注定孤独的，坚持下来就会看到明天的太阳。回顾 showImg(https://user-...

li21 2019-07-01 10:26 评论0 收藏0
剑指offer(javascript版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。 1.二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数...

imtianx 2019-08-20 15:20 评论0 收藏0