105. Construct Binary Tree from Preorder and Inorder Traversal

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

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

------------------------------------------------------------------------------

给定先序遍历和中序遍历结果，要求还原二叉树

preorder的第一个肯定是根节点，那么只要找到根节点在inorder中的位置，inorder就可以被划分开来左右子树。

递归做法：

/**
 * 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) {
        return dfs(0, preorder.length, 0, inorder.length - 1, preorder, inorder);
    }

    public TreeNode dfs(int preStart, int preEnd, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preStart]);
        int inIndex = -1; // Index of current root in inorder
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == root.val) {
                inIndex = i;
                break;
            }
        }
        root.left =  dfs(preStart+1,preStart+inIndex-inStart, inStart,inIndex-1, preorder,inorder);
        root.right = dfs(preStart+inIndex-inStart+1,preEnd,  inIndex+1,inEnd,   preorder,inorder);
        return root;
    } 
}

由于每次都需要在inorder中找出根节点的位置，我们可以预先构造一个HashMap来实现快速查找，以达到加速目的

/**
 * 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) {
        Map<Integer,Integer> inorderMap = new HashMap<Integer,Integer>();
        for(int i = 0;i<inorder.length;i++){
            inorderMap.put(inorder[i],i);
        }
        
        return dfs(0,preorder.length-1,  0,inorder.length-1, inorderMap, preorder,inorder);
    }
    private TreeNode dfs(int preStart,int preEnd,  int inStart,int inEnd, Map<Integer,Integer> inorderMap, int[] preorder,int[] inorder){
        if(preStart>preEnd || inStart>inEnd) return null;
        
        TreeNode root = new TreeNode(preorder[preStart]);
        
        int rootIndexAtInorder = inorderMap.get(root.val);
        
        root.left =  dfs(preStart+1, preStart+rootIndexAtInorder-inStart,  inStart,rootIndexAtInorder-1,  inorderMap,  preorder,inorder);
        root.right = dfs(preStart+rootIndexAtInorder-inStart+1,preEnd,     rootIndexAtInorder+1,inEnd,    inorderMap,  preorder,inorder);
        return root;
    }
}