题目描述

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

示例1：

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例2：

Input: preorder = [-1], inorder = [-1]
Output: [-1]

思路

分治思想，递归构造树。

对于中序遍历：对于某个结点，在中序遍历中的位置假设是3，那么位置0~2都是在该结点的左子树上，4~结尾都是在该结点的右子树上。

对于前序遍历：第一个结点就是跟结点。

举个例子：

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

首先，preorder的第一个结点是3，那么该结点就是整个树的根节点。然后，去找3在中序遍历中的位置，发现下标为1，那么下标为0的都在3的左子树上，下标大于1的都在右子树上。即， 左子树：

preorder = [9]
inorder = [9]

右子树：

preorder = [20, 15, 7]
inorder = [15, 20, 7]

左子树只有一个节点了，直接连接。
那么右子树，又按照同样的方式构造，取preorder的第一个元素，去inorder中找下标。

小技巧：

• 在inorder中能知道左边有多少个结点，那么对应的，去preorder中找相同数量的结点即可。
• 真正做这段道题时，需要用到多个下标，和下标的转换关系，建议记好思路以后画一个图来保证下标转化正确。
• 两个数组都是左闭右开，记住就好。
• 用map来保存inorder的下标，减少时间复杂度。

class Solution {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // map保存下标
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 参数为两个数组和两组下标。
        // 左闭右开，所以传length
        TreeNode node = helpder(preorder, 0, preorder.length, inorder, 0, inorder.length);
        return node;
    }
    private  TreeNode helpder(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end) {
        if (p_start == p_end) {
            return null;
        }
        int val = preorder[p_start];
        TreeNode root = new TreeNode(val);
        int root_idx = map.get(val);
        int left_num = root_idx - i_start;
        // 同样的，右边是开的，所以是p_start + left_sum + 1和root_idx;
        // 以及p_end和i_end
        root.left = helpder(preorder, p_start + 1, p_start + left_num +1, inorder, i_start, root_idx);
        root.right = helpder(preorder, p_start + left_num + 1, p_end, inorder, root_idx + 1, i_end);
        return root;
    }
}