105. Construct Binary Tree from Preorder and Inorder Traversal

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

Solution1: Recursive做法

Example:
          1
     2        3
  4    5    6    7
8  9      10

In order:  8 4 9 2 5 1* 10 6 3 7
Preorder: 1* 2 4 8 9 5  3 6 10 7

与106题 http://www.jianshu.com/p/bacca777b12b 类似

思路：
Preorder的第一位是根节点，顺序:根节点，左树，右树；Inorder顺序：左树，根节点，右树。
利用此特性，每次在每一段pretorder序列中，得到第一位元素，在inorder序列中查找此元素位置pos，inorder序列中pos的前、后部分a(8 4 9 2 5)、b(10 6 3 7)分别作为下次递归的inorder序列input；
并利用a、b部分的长度/位置在pretorder序列中找到相应部分c(2 4 8 9 5)、d(3 6 10 7)，作为下次递归的postorder序列input。
重复此过程(Top-down Recursion)。
在inorder查找的过程利用hashmap，故
Time Complexity: O(N) Space Complexity: O(N)

Solution2: Iterative做法

思路：

Solution1 Code：

class Solution1 {
    private HashMap<Integer, Integer> inorder_map = new HashMap<Integer, Integer>();
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (inorder == null || preorder == null || inorder.length != preorder.length)
            return null;

        // build hashmap from Inorder array
        for (int i = 0; i < inorder.length; ++i) {
            inorder_map.put(inorder[i], i);
        }

        // recursively build the tree
        return build(inorder, 0, inorder.length - 1, preorder, 0, preorder.length - 1);
    }    
    
    public TreeNode build(int[] inorder, int in_start, int in_end, int[] preorder, int pre_start, int pre_end) {
        if(in_start > in_end || pre_start > pre_end)
            return null;

        int root_value = preorder[pre_start];
        TreeNode root = new TreeNode(root_value);

        int pos_inorder = inorder_map.get(root_value);
        int pre_left_length = pos_inorder - in_start;
        root.left = build(inorder, in_start, pos_inorder - 1, preorder, pre_start + 1, pre_start + pre_left_length);
        root.right = build(inorder, pos_inorder + 1, in_end, preorder, pre_start + pre_left_length + 1, pre_end);

        return root;

    }
}

Solution1.Round1 Code：

class Solution {
    
    private Map<Integer, Integer> in_map;
    
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        
        in_map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) {
           in_map.put(inorder[i], i);
        }
        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        
    }
    
    private TreeNode helper(int[] preorder, int pre_start, int pre_end, int[] inorder, int in_start, int in_end) {
        if(pre_start > pre_end || in_start > in_end) {
            return null;
        }
            
        int root_val = preorder[pre_start];
        int root_in_index = in_map.get(root_val);
        
        TreeNode node = new TreeNode(root_val);
        
        int relat_root_in_index = root_in_index - in_start;
        node.left = helper(preorder, pre_start + 1, pre_start + 1 + relat_root_in_index - 1, inorder, in_start, root_in_index - 1);
        node.right = helper(preorder, pre_start + 1 + relat_root_in_index, pre_end, inorder, root_in_index + 1, in_end);
        
        return node; 
    }
}

change End to 元素边界

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) return null;
        
        Map<Integer, Integer> in_map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) {
            in_map.put(inorder[i], i);
        }
        
        return dfsBuild(in_map, preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    
    private TreeNode dfsBuild(Map<Integer, Integer> in_map, int[] preorder, int pre_s, int pre_e, int[] inorder, int in_s, int in_e) {
        if(pre_s == pre_e || in_s == in_e) return null;
        int cur_val = preorder[pre_s];
        int in_index = in_map.get(cur_val);
        int rela_in_index = in_index - in_s;
        
        TreeNode root = new TreeNode(cur_val);
        root.left = dfsBuild(in_map, preorder, pre_s + 1, pre_s + 1 + rela_in_index, inorder, in_s, in_index);
        root.right = dfsBuild(in_map, preorder, pre_s + 1 + rela_in_index, pre_e, inorder, in_index + 1, in_e);

        return root;
    }
}