106 Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

1. Question

Given inorder and postorder traversal of a tree, construct the binary tree.

2. Implementation

(1) Recursion

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0 || postorder == null || postorder.length == 0) {
            return null;
        }

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

        return constructTree(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

    public TreeNode constructTree(int[] postorder, int postStart, int postEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> map) {
        if (postStart > postEnd || inStart > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(postorder[postEnd]);

        int index = map.get(root.val);

        root.left = constructTree(postorder, postStart, postStart + (index - inStart) - 1, inorder, inStart, index - 1, map);
        root.right = constructTree(postorder, postStart + (index - inStart), postEnd - 1, inorder, index + 1, inEnd, map);
        return root;
    }
}

3. Time & Space Complexity

Recursion: 时间复杂度O(n^2)，如果tree是skewed, 当tree是balanced，时间复杂度是O(nlogn)，空间复杂度是O(n)，因为map