leetcode-重建二叉树

刷leetcode《剑指offer》中第七题“重建二叉树”，以下记录一下解题思路。

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

给出以下的前序以及中序遍历结果

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

解析

前序遍历的首个元素即为根节点 root 的值；
在中序遍历中搜索根节点 root 的索引，可将中序遍历划分为[ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。
根据前序以及中序可以知道，根节点肯定是前序遍历的第一个节点。由根节点可以找到中序遍历的位置，从而可以构建其左子树、右子树。由图可以知道，使用分治法思想，将其划分为每个小部分，进行递归。

注意

题目的重点部分来源于对递归的条件以及递归的参数的取舍。

递归的条件（当左边大于右边就会越界，就证明没有节点）
```
 if (preL > preR || inoL > inoR) {
     return null;
  }
```
递归参数取舍

解决: 取1在中序遍历的位置为pivot，设9的位置为x，可列x - (preL+1)=pivot-1-inL，可以得到9的位置，从而使用分治算法，切割左右子树。
```
 // 构建左子树
 root.left = buildTree(preL + 1, index - inoL + preL, inoL, index - 1);
 // 构建右子树
 root.right = buildTree(index - inoL + preL + 1, preR, index + 1, inoR);
```

具体实现代码

/**
 * 重建二叉树，有前序遍历结果以及中序遍历结果
 *    3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 */
class Solution {

    // 利用空间换时间
    HashMap map = new HashMap();
    int[] pre;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preL = preorder.length;
        int inoL = inorder.length;
        pre = preorder;
        // 将中序遍历存入map中
        for (int i = 0; i < inoL; i++) {
            map.put(inorder[i], i);
        }
        return buildTree(0, preL - 1, 0, inoL - 1);
    }

    /**
     * @param preL 前序遍历左端
     * @param preR 前序遍历右端
     * @param inoL 中序遍历左端
     * @param inoR 中序遍历右端
     * @return
     */
    private TreeNode buildTree(int preL, int preR, int inoL, int inoR) {
        if (preL > preR || inoL > inoR) {
            return null;
        }
        // 构建二叉树的根节点，必须是前序遍历的第一个节点
        TreeNode root = new TreeNode(pre[preL]);
        // 找到根节点在中序遍历的位置
        int index = (int) map.get(pre[preL]);
        // 构建左子树
        root.left = buildTree(preL + 1, index - inoL + preL, inoL, index - 1);
        // 构建右子树
        root.right = buildTree(index - inoL + preL + 1, preR, index + 1, inoR);
        return root;
    }
}