[剑指offer] 重建二叉树

题目描述

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

解题思路

我们知道,前序遍历的第一个节点就是树的根节点,所以我们先根据前序遍历序列的第一个数字创建根结点,接下来在中序遍历序列中找到根结点的位置,根节点的左边就是左子树,右边就是右子树,这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后,就可以递归地去分别构建它的左右子树。

参考代码

/**
 * 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;
        return ConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public TreeNode ConstructBinaryTree(int [] pre, int ps, int pe, 
int [] in, int is, int ie){
        if(ps > pe || is > ie){
            return null;
        }
        TreeNode root = new TreeNode(pre);
        for(int i = is; i<=ie; i++){
            if(in[i] == pre){
                root.left = ConstructBinaryTree(pre, ps+1, ps+i-is, in, is, i-1);
                root.right = ConstructBinaryTree(pre, ps+i-is+1, pe, in, i+1, ie);
                break;
            }
        }
        return root;
    }
}

版权属于: 尾尾部落

原文地址: https://weiweiblog.cn/reconstructbinarytree/

转载时必须以链接形式注明原始出处及本声明。

window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"1","bdSize":"24"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[剑指offer] 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

9520
来自专栏计算机视觉与深度学习基础

Leetcode 173 Binary Search Tree Iterator

mplement an iterator over a binary search tree (BST). Your iterator will be ini...

21860
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

22090
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

14610
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

24350
来自专栏猿人谷

双向链表

双向链表       在线性链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表...

27650
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

21570
来自专栏Java爬坑系列

【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

  TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

10920
来自专栏Java爬坑系列

【Java入门提高篇】Day31 Java容器类详解(十三)TreeSet详解

  TreeSet是Set家族中的又一名懒将,跟其他两位一样,与对应的Map关系密不可分

9830
来自专栏zhisheng

SimpleDateFormat 如何安全的使用?

看到这条我立马就想起了我实习的时候有个项目里面就犯了这个错误,记得当时是这样写的:

11110

扫码关注云+社区

领取腾讯云代金券