leetcode: 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.

原问题链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

 

问题分析

　　这个问题看似没有很明确的思路，但是根据树前序和中序遍历的序列，我们还是可以得到一个规律。我们知道，对树的前序遍历来说，它是首先遍历当前节点，然后递归的去遍历它的左子节点，再去遍历它的右子树。而对于中序遍历来说，它是首先遍历当前节点的左子树，再遍历当前节点，然后再遍历它的右子树。

　　从上面遍历的规律来看，对于一个前序遍历的序列，它的第一个节点必然就是当前树的根节点。而对于中序遍历序列来说，如果我们找到了这个节点的话，因为它是先左边再中间再右边的。这个根节点就将中序遍历的序列划分成两边。一边对应着根节点的左子树，另外一边对应着根节点的右子树。对于中序的序列来说，从开始节点到这个根节点的距离就是左子树的元素个数。在对应的前序序列里，在当前节点后面的同样个数的元素就应该是这个节点的左子树里的元素。有了这一步的基础，我们对于它们划分的两个左右子树再递归的运用上面的方法，就可以得到最终的结果了。

　　从实现的角度来说，我们定义一个函数buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder)。这里preStart表示前序遍历的当前节点元素位置，inStart, inEnd分别表示中序遍历的起点和终点。在preStart >= preorder.length || inStart > inEnd的时候，表示函数退出的条件。我们取preorder[preStart]这个位置的元素构造一个树节点。而它的左右子节点的构造则分别是buildTree(preStart + 1, intStart, i - 1, preorder, inorder)和buildTree(preStart + i - inStart + 1, i + 1, inEnd, preorder, inorder)。这里i的值是根据当前preorder[preStart]的值找到inorder里对应值的索引。为了让找这个索引的速度快点，我们可以首先遍历inorder，将每个值和它的索引位置构造成一个Map<String, String>，这样以后每次直接到里面取就可以了。

　　详细的代码实现如下：

 

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = buildInOrderMap(inorder);
        return buildTree(0, 0, inorder.length - 1, preorder, inorder);
    }
    
    private TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if(preStart >= preorder.length || inStart > inEnd) return null;
        TreeNode node = new TreeNode(preorder[preStart]);
        int i = map.get(preorder[preStart]);
        node.left = buildTree(preStart + 1, inStart, i - 1, preorder, inorder);
        node.right = buildTree(preStart + i - inStart + 1, i + 1, inEnd, preorder, inorder);
        return node;
    }
    
    private Map<Integer, Integer> buildInOrderMap(int[] inorder) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i], i);
        return map;
    }
}