重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例

二叉树

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

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

思考：

提示

• 前序遍历顺序：根、左、右；中序遍历顺序：左、根、右；

• 根据前中顺序构建二叉树

  前序的第一个元素为树的根节点，根据这个根节点，将中序遍历划分为左、右两部分

  然后根据左右两部分的数量，可以将前序遍历从左到右划分为根节点、左子树、右子树

• 对左右子树进行递归

题解：

class Solution {

    HashMap<Integer, Integer> map = new HashMap<>();
    //保存方便递归
    int[] preorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        this.preorder = preorder;
        //保存中序遍历key value
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        //(根节点，数组左边界，数组右边界)
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int root,int left,int right){
        //递归条件
        if(left > right) return null;

        TreeNode node = new TreeNode(preorder[root]);

        int i = map.get(preorder[root]);

        node.left = recur(root+1, left, i-1);
        //右子树根 = 当前根 + 左子树数量 + 1
        node.right = recur(root+(i-left)+1, i+1, right);
        return node;
    }
}