难度中等353收藏分享切换为英文接收动态反馈
    输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

    例如，给出
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：
    3
    / \
    9 20
    / \
    15 7

    限制：
    0 <= 节点个数 <= 5000

    /*
     Definition for a binary tree node.
    public class TreeNode {
     int val;
    TreeNode left;
     TreeNode right;
    TreeNode(int x) { val = x; }
     }
    */
    class Solution {

    1. //索引map，为了找中心根节点<br />    private Map<Integer,Integer> indexMap;
    3. //递归建立<br />    TreeNode TreeBuild(int[] preorder,int[] inorder,int p_l,int p_r,int i_l,int i_r){<br />        if (p_l > p_r){<br />        //左子树为空<br />            return null;<br />        }<br />        //前序遍历的第一个数为根节点,根节点在前序列的索引<br />        int p_root = p_l;<br />        //中序遍历定位根节点,通过值引入索引map找在中序中位置<br />        int i_root =  indexMap.get(preorder[p_root]);
    5.     //将根节点建立<br />        TreeNode root = new TreeNode(preorder[p_root]);<br />        //得到左子树的额总数<br />        int size_l = i_root - i_l;//初次i_l肯定为零<br />        //构造左子树并连接到根节点<br />        //先序遍历中从左边界+1（因为最前为根节点）到size_l的元素与中序中从i_l到i_root—1的元素相对应<br />        root.left = TreeBuild(preorder,inorder,p_l+1,p_l+size_l,i_l,i_root-1);<br />        //先序遍历的<br />        root.right = TreeBuild(preorder,inorder,p_l+size_l+1,p_r,i_root+1,i_r);<br />        return root;<br />    }
    7. public TreeNode buildTree(int[] preorder, int[] inorder)    {<br />        int num = inorder.length;<br />        indexMap = new HashMap<Integer,Integer>();<br />        for (int i=0;i<num;i++){<br />            //值，索引<br />            indexMap.put(inorder[i],i);<br />        }<br />        return TreeBuild(preorder,inorder,0,num-1,0,num-1);
    9. }<br />}