重建二叉树

import java.util.HashMap;
public class Solution {
    public TreeNode reConstructBinaryTree(int[] preorder, int[] inorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        //[0,preorder.length) 左开右闭，所以后面都是统一的
        return buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
    }


    private TreeNode buildTreeHelper(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);
        int i_root_index = map.get(root_val);
        //左子树
        int leftNum = i_root_index - i_start;

        /*
         * 辅助记忆边界:
         * 从画图你会发现。下面的两个比较复杂的边界。连起来就是
         * [p_start+1,p_end)
         * [i_start,i_root_index) [i_root_index+1,i_end)
         * 两个都少了一个范围，这个范围就是每颗子树的根节点。所以如果边界范围不太好记，可以画图
         * 或者往这方面想
         */
        root.left = buildTreeHelper(preorder, p_start + 1, p_start + leftNum + 1, inorder, i_start, i_root_index, map);
        root.right = buildTreeHelper(preorder, p_start + leftNum + 1, p_end, inorder, i_root_index + 1, i_end, map);
        return root;
    }

}

时间复杂度：O(n)
代码应该写的算是比较明白的，直接看代码