Poison

105. Construct Binary Tree from Preorder and Inorder Traversal

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // preorder: root, left, right
        // inorder: left, root, right

        Map<Integer, Integer> inOrderValueToIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inOrderValueToIndexMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inOrderValueToIndexMap);
    }

    private TreeNode buildTree(int[] preorder, int preStartIndex, int preEndIndex, int[] inorder, int inStartIndex, int inEndIndex, Map<Integer, Integer> inOrderValueToIndexMap) {
        if (preStartIndex > preEndIndex) {
            return null;
        }

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

        int inRootIndex = inOrderValueToIndexMap.get(root.val);
        int leftTreeNodeCount = inRootIndex - inStartIndex;

        root.left = buildTree(preorder, preStartIndex + 1, preStartIndex + 1 + leftTreeNodeCount - 1, inorder, inStartIndex, inRootIndex - 1, inOrderValueToIndexMap);
        root.right = buildTree(preorder, preStartIndex + 1 + leftTreeNodeCount - 1 + 1, preEndIndex, inorder, inRootIndex + 1, inEndIndex, inOrderValueToIndexMap);
        return root;
    }
}
Reference

105. Construct Binary Tree from Preorder and Inorder Traversal
剑指 Offer 07. 重建二叉树