Poison

106. Construct Binary Tree from Inorder and Postorder 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
28
29
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // inorder: left, root, right
        // postorder: left, right, root

        Map<Integer, Integer> valueToInOrderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            valueToInOrderIndexMap.put(inorder[i], i);
        }

        return buildTree(valueToInOrderIndexMap, inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    private TreeNode buildTree(Map<Integer, Integer> valueToInOrderIndexMap, int[] inorder, int startInOrderIndexInclusive, int endInOrderIndexInclusive, int[] postorder, int startPostOrderIndexInclusive, int endPostOrderIndexInclusive) {
        if (startInOrderIndexInclusive > endInOrderIndexInclusive) {
            return null;
        }

        int rootValue = postorder[endPostOrderIndexInclusive];
        int rootIndexInInOrder = valueToInOrderIndexMap.get(rootValue);
        int leftTreeNodeCount = rootIndexInInOrder - startInOrderIndexInclusive; // 注意此处不能 +1, 因为是使用 root 节点的下标去减的

        TreeNode rootNode = new TreeNode(rootValue);
        rootNode.left = buildTree(valueToInOrderIndexMap, inorder, startInOrderIndexInclusive, rootIndexInInOrder - 1, postorder, startPostOrderIndexInclusive, startPostOrderIndexInclusive + leftTreeNodeCount - 1);
        rootNode.right = buildTree(valueToInOrderIndexMap, inorder, rootIndexInInOrder + 1, endInOrderIndexInclusive, postorder, startPostOrderIndexInclusive + leftTreeNodeCount, endPostOrderIndexInclusive - 1);

        return rootNode;
    }
}
Reference

106. Construct Binary Tree from Inorder and Postorder Traversal