图解「剑指Offer」之用前序和中序遍历序列构建二叉树

前序遍历 preorder = [28，16，13，22，30，29，43]
中序遍历 inorder = [13，16，22，28，29，30，43]

         28
       /    \
     16     30
    /  \    /  \
   13  22  29  43

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//author:程序员小吴
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       //借助哈希表来储存二叉树的节点，优化时间复杂度
       Map<Integer, Integer> inPos = new HashMap<>();
       for (int i = 0; i < inorder.length; ++i){
            inPos.put(inorder[i], i);
       }
       return buildTree(preorder, 0, preorder.length-1, 0, inPos);
    }

    private TreeNode buildTree( int[] pre, int preStart , int preEnd, int inStart, Map<Integer, Integer> inPos) {
    //递归停止条件
    if (preStart > preEnd) return null; 
    //前序中左起第一位肯定是根结点
    TreeNode root = new TreeNode(pre[preStart]);
    //根结点的位置直接通过中序获取
    int rootIdx = inPos.get(pre[preStart]);
    //左子树结点个数可以通过中序中根节点的位置与中序中起始位置确定
    int leftLen = rootIdx - inStart;
    //递归调用
    root.left = buildTree(pre, preStart + 1, preStart + leftLen, inStart, inPos);
    root.right = buildTree(pre, preStart + leftLen + 1, preEnd, rootIdx + 1, inPos);
    return root;
  }
}