【算法训练-二叉树 二】【重建二叉树】依据前序与中序遍历序列重建二叉树

import java.util.*;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    // 0 设置中序遍历 值-元素位置 的map，因为题目确保了无重复元素
    private Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param preOrder int整型一维数组
     * @param vinOrder int整型一维数组
     * @return TreeNode类
     */
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        // 1 条件判断
        if (preOrder == null || preOrder.length < 1 || vinOrder == null ||
                vinOrder.length < 1) {
            return null;
        }
        // 2 构建中序遍历的哈希映射
        int length = preOrder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(vinOrder[i], i);
        }
        // 递归获取左右子树
        return rebuildTree(preOrder, 0, length - 1, vinOrder, 0, length - 1);
    }
    private TreeNode rebuildTree(int[] preOrder, int preLeft, int preRight,
                                 int[] inOrder, int inLeft, int inRight) {
        // 0 设置递归终止条件
        if (preLeft > preRight) {
            return null;
        }
        // 1 首先构建根节点，也就是前序遍历的第一个元素
        TreeNode root = new TreeNode(preOrder[preLeft]);
        // 找到根节点在中序集合中的位置
        int pIndex = indexMap.get(preOrder[preLeft]);
        // 明确左子树的节点数量
        int leftSize = pIndex - inLeft;
        // 2 递归构建根节点的左子树:
        root.left = rebuildTree(preOrder, preLeft + 1, preLeft + leftSize,
                                inOrder, inLeft, pIndex - 1);
        // 3 递归构建根节点的右子树:
        root.right = rebuildTree(preOrder, preLeft + leftSize + 1, preRight,
                                 inOrder, pIndex + 1, inRight);
        return root;
    }
}