105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

思路

递归构建树
中序数组索引优化1(数组统计中序数组索引)
中序数组索引优化2(哈希表统计中序数组索引)
迭代

代码

递归构建树

class Solution {
    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeFunction(preorder, inorder, 0, preorder.length - 1, 0);
    }

    //递归构建树，count为偏移量
    private TreeNode buildTreeFunction(int[] preorder, int[] inorder, int start, int end, int count) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        //在中序数组中找到根节点索引下标
        int index = end - count;
        while (inorder[index] != root.val) {
            index--;
        }
        index += count;
        //左
        root.left = buildTreeFunction(preorder, inorder, start + 1, index, count + 1);
        //右
        root.right = buildTreeFunction(preorder, inorder, index + 1, end, count);
        return root;
    }
}

中序数组索引优化1

class Solution {
    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int[] indexes = new int[6000];
        for (int i = 0; i < inorder.length; i++) {
            indexes[inorder[i] + 3000] = i;
        }
        return buildTreeFunction(preorder, inorder, 0, preorder.length - 1, 0, indexes);
    }

    //递归构建树
    private TreeNode buildTreeFunction(int[] preorder, int[] inorder, int start, int end, int count, int[] indexes) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        //在中序数组中找到根节点索引下标
        int index = indexes[root.val + 3000] + count;
        //左
        root.left = buildTreeFunction(preorder, inorder, start + 1, index, count + 1, indexes);
        //右
        root.right = buildTreeFunction(preorder, inorder, index + 1, end, count, indexes);
        return root;
    }
}

中序数组索引优化2(哈希表统计中序数组索引)

class Solution {
    private Map<Integer, Integer> map;
    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return buildTreeFunction(preorder, inorder, 0, preorder.length - 1, 0);
    }

    //递归构建树
    private TreeNode buildTreeFunction(int[] preorder, int[] inorder, int start, int end, int count) {
        if (start > end) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[start]);
        //在中序数组中找到根节点索引下标
        int index = map.get(root.val) + count;
        //左
        root.left = buildTreeFunction(preorder, inorder, start + 1, index, count + 1);
        //右
        root.right = buildTreeFunction(preorder, inorder, index + 1, end, count);
        return root;
    }
}

迭代

class Solution {
    //105. 从前序与中序遍历序列构造二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //题意长度最少为1
//        if (preorder == null || preorder.length == 0) {
//            return null;
//        }
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}