剑指offer：重建二叉树

发表于 | 分类于

前言

　　树也是一种重要的数据结构，它的逻辑是：除了根节点之外每个节点都只有一个父节点，根节点没有父节点，除了叶节点之外所有的节点都有一个或多个字节点。我们经常用到的是二叉树（还包括一些特殊的二叉树：二叉搜索树、大小根堆、红黑树等使用也广泛），它的遍历方式有前序遍历、中序遍历、后序遍历、宽度优先遍历。知道中序遍历和前后遍历任意其他一个，我们就能重建二叉树，这题就是已经前中序要求重建二叉树。

重建二叉树

题目

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

分析

       我们知道在二叉树的前序遍历中，第一个总是根值。中序遍历中，根节点的值在序列的中间。左子树的根节点位于根节点的左边，右子树的结点在根节点的右边，因此我们需要扫描中序遍历才能找到根节点的值。找到根结点之后，中序遍历分成两部分，分别是左右子树的中序遍历，而我们在前序遍历中根据左右子树的个数就能确定左右子树的前序遍历，因此我们就能递归的完成。具体步骤如下：

  1. 先进行输入序列的检查。
  2. 把中序序列放入一个hashmap，值为key，索引为value，这样很方便的通过前序序列中的值得到在中序遍历中的索引，很巧妙，而且时间复杂度较低。
  3. 利用递归完成树重建，为了代码的简洁性，写了preIn函数完成功能。具体输入参数和意义如下注释部分。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    //为空则返回空，输入检查，还可检查两者长度是否相等。
    if(pre==null||in==null){
          return null;
    }   
    java.util.HashMap<Integer,Integer> map=new java.util.HashMap<Integer,Integer>();
    //中序遍历进map
    for(int i=0;i<in.length;i++){
       map.put(in[i],i); 
    }
    //交给重建函数
    return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
}
//p，n，map属于不变的，这样写代码简洁一点，变得是前序遍历和中序遍历在原序列中的起止索引。
public TreeNode preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,java.util.HashMap<Integer,Integer> map){
    //前序遍历开始位置大于结束位置，返回空。
    if(pi>pj){
        return null;
    }
    //前序遍历开始位置就是根节点。
    TreeNode head =new TreeNode(p[pi]);
    //获得根节点在中序序列中的索引位置
    int index=map.get(p[pi]);
    //递归左子树，前序遍历pi自增1就行，结束位置算法是（pi+1）+（index-1-ni），因为
    //index-1为中序遍历结束位置减去ni开始位置就是中序遍历的个数，在加上pi+1就是前序遍历
    //结束为止
    head.left=preIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
    //右子树的前序开始位置为左子树结束位置自增1，结束位置是pj，中序遍历开始是根节点位置自
    //增1，结束位置是nj
    head.right=preIn(p,pi+index-ni+1,pj,n,index+1,nj,map);
    //重建完成返回
    return head;
}