重建二叉树

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下二叉树：

  3
 / \
9  20
  /  \
 15   7

解题思路

根据preorder和inorder重建二叉树。

已知：

前序pre ：根、左、右。
中序in  ：左、根、右。

每一次的递推传递的参数：

参数	含义
rootIndex	根节点的前序索引
left	中序数组中的左边界
right	中序数组中的右边界

每次递推中如何确定二叉树？
首先将中序的数组及其索引保存到哈希表{inorder[index],index}，减少后续的读取时间。

1.递归的结束条件：left>right 左边界大于右边界则说明越过了叶子结点，即返回空。

2.如果当前没有越过叶子结点，则root = new TreeNode(preorder[rootIndex])就是当前的结点，

	根节点索引	中序左边界	中序右边界
左子树	rootIndex+1	left	index-1
右子树	rootIndex+index-left+1	index+1	right

3.返回root。

代码（Java）

import java.util.*;
public class Solution {
    int[] preorder;
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length==0||in.length==0) return null;
        preorder=pre;
        
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return reBuild(0,0,in.length-1);
    }
    public TreeNode reBuild(int rootIndex,int left,int right){
        if(left>right){return null;}
        
        int inorderIndex=map.get(preorder[rootIndex]);
        
        TreeNode root=new TreeNode(preorder[rootIndex]);
        
        root.left=reBuild(rootIndex+1,left,inorderIndex-1);
        root.right=reBuild(rootIndex+inorderIndex-left+1,inorderIndex+1,right);
        
        return root;
    }
}