本文共 1657 字，大约阅读时间需要 5 分钟。

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       // 初始化字段：前序、中序、当前要处理的前序遍历首元素（每次处理完后该值加1，即处理下一个根结点）    int[] preorder;    int[] inorder;    int preFront;    // 根据中序生成的哈希表，方便确定左右子结点数量    Map
   
     inorderMap = new HashMap
    
     ();    // 返回一个创建好二叉树的结点 的辅助递归函数：特殊情况、返回值    public TreeNode helper(int inLeft,int inRight){
           if(inLeft > inRight){
               return null;        }        // 获取前序遍历的首结点的值再生成新的根节点        int rootVal = preorder[preFront++];        TreeNode root = new TreeNode(rootVal);        // 找到其在中序遍历中的位置下标        int rootIndex = inorderMap.get(rootVal);        // 根据前序遍历特点，左子树排前面，优先处理。根据得到的下标确定子树的范围        root.left = helper(inLeft,rootIndex-1);        root.right = helper(rootIndex+1,inRight);        return root;    }    public TreeNode buildTree(int[] preorder, int[] inorder) {
           this.preorder = preorder;        this.inorder = inorder;        preFront = 0;        // i 是辅助变量表示下标，给map添加元素用的;其中键时结点值，更方便get得到下标        int i = 0;        for(int val:inorder){
               inorderMap.put(val,i++);        }        return helper(0,inorder.length-1);    }}
    
   

之前刷过的题目，还有许多细节要注意。

• 前序遍历是 根左右，所以第一个就是二叉树的根节点，子树也一样。
• 中序遍历是 左根右，通过前序遍历确定的根节点，在中序遍历中找到后即可确定子树范围，在根节点左边的就是其左子树，右边就是右子树。
• 二叉树的特性一般使用递归可能性较高；这里使用的是一个辅助递归函数，还添加了类的字段，即假设我们有一个哈希表可以知道结点在中序遍历的位置，只需要给递归函数明确我们要重建二叉树的左右下标范围即可。

关于递归还是需要注意这几点：

• 函数的作用，根据中序遍历的下标返回构建好的二叉树根结点
• 特殊情况，这里的是左下标大于右下标，说明为空树
• 最小子问题：根据前序先获得根结点，再利用哈希表找其在中序的位置，明确左右子树范围递归构建。注意每次在前序获取根节点后，将指向前序首元素的指针preFront往后挪一位，指向新的根节点。同时构建的顺序要先左后右，这是有前序遍历的特点确定的。

转载地址：http://lsozi.baihongyu.com/