105 Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

1. Question

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

2. Implementation

(1) Recursion

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.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(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
    }

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

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

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

        root.left = constructTree(preorder, preStart + 1, preStart + (index - inStart), inorder, inStart, index - 1, map);
        root.right = constructTree(preorder, preStart + 1 + (index - inStart), preEnd, inorder, index + 1, inEnd, map);
        return root;
    }
}

(2) Iteration

3. Time & Space Complexity

Recursion: 时间复杂度O(n^2), 当树是skewed的时候，平均时间是O(nlogn), 空间复杂度O(n)，因为用了map