详解重构二叉树

本质上就是前序遍历的框架。
前序数组的第一个是根节点，找到中序数组它的索引 （可用map降低时间复杂度），中序数组以它为中心，左边是左子树，右边是右子树。
将大问题化成小问题，利用递归。 而指针可以在每轮递归中作为通信的工具。
上一层递归告诉下一层“你该缩小范围找了”。
left每一层递归返回给上一层的是刚刚遍历完的根节点的下一个，而right返回的是刚刚遍历完的（根节点当前位置 + 左子树的节点个数）的下一个。这跟前序数组的前序遍历性质有关，而我们又是基于前序数组来重构二叉树的。

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //用map来缓存值和对应的索引，方便在递归方法中查找，降低时间复杂度
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i] , i);
        }
        return builTree(preorder, 0, preorder.length, inorder, 0, inorder.length, map);

    }
    private TreeNode builTree(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end, HashMap<Integer, Integer> map){
        //递归出口 当指针相等时，左右子树已经找完了
        if(p_start == p_end)
            return null;

        int root_val = preorder[p_start];
        //构建节点
        TreeNode root = new TreeNode(root_val);
        //找到索引，利用这个位置将数组分成2部分， 前序数组的左部分就是左子树 
        int i_root_index = map.get(root_val);
        int leftNum = i_root_index - i_start;

        //前序遍历 注意左右子树的索引 start和end区间就是一个子树
        root.left = builTree(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
        root.right = builTree(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
        return root;
    }
}