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

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

解题思路

1. 前序数组首元素为根，在中序数组中定位其位置以划分左右子树区间，再各自切分出对应的子前序与子中序数组，递归构建左右子树并接到根上
2. 用哈希表 O(1) 定位前序首元素在中序数组中的位置，据此算出左子树节点数，将前序与中序区间各划分为左右两部分，递归构建左右子树并接到根上

参考代码

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        int index = 0;
        for(int i = 0; i < inorder.length; i ++) {
            if(root.val == inorder[i]) {
                index = i;
                break;
            }
        }
        int len = preorder.length;
        int[] left_preorder = Arrays.copyOfRange(preorder, 1, index + 1);
        int[] left_inorder = Arrays.copyOfRange(inorder, 0, index);
        root.left = buildTree(left_preorder, left_inorder);
        int[] right_preorder = Arrays.copyOfRange(preorder, index + 1, len);
        int[] right_inorder = Arrays.copyOfRange(inorder, index + 1, len);
        root.right = buildTree(right_preorder, right_inorder);
        return root;
    }
}

哈希表优化

class Solution {
    private Map<Integer, Integer> indexMap;
    private int[] preorder;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        int len = preorder.length;
        indexMap = new HashMap<>(len);
        this.preorder = preorder;
        for(int i = 0; i < len; i ++) {
            indexMap.put(inorder[i], i);
        }
        return build(0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode build(int preL, int preR, int inL, int inR) {
        if(preL > preR || inL > inR) {
            return null;
        }
        int rootVal = preorder[preL];
        TreeNode root = new TreeNode(rootVal);
        int index = indexMap.get(rootVal);

        int leftSize = index - inL;
        root.left = build(preL + 1, preL + leftSize, inL, index - 1);
        root.right = build(preL + leftSize + 1, preR, index + 1, inR);
        return root;
    }
}