题解 | #牛群的树形结构重建II#

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *前序 根-》左-》右
     中序  左-》根-》右
	 由遍历顺序可知前序的第一个节点为根节点，在中序遍历中找到根节点，那么中序根节点左边的为左子树，右边的为右子树，反复迭代处理即可。
	 假设中序遍历的根节点坐标为 index，那么左子树的个数为 sub = index - instart 由此可得到边界值
	 前序左子树 开始- prestart+1,结束-perstart+sub
	 中序左子树 开始-inStart,结束-index-1
	 前序右子树 开始-prestart+sub+1,结束-preEnd
	 中序右子树 开始-index+1,结束-inEnd
	 
	 
     * @param preOrder int整型一维数组
     * @param inOrder int整型一维数组
     * @return TreeNode类
     */
    HashMap<Integer, Integer> map = new HashMap<>();
    int[] pre;
    public TreeNode buildTreeII (int[] preOrder, int[] inOrder) {
        for (int i = 0; i < inOrder.length; i++) {
            map.put(inOrder[i], i);
        }
        pre = preOrder;
        return buildTree(0, preOrder.length - 1, 0, inOrder.length - 1);
    }

    public TreeNode buildTree(int preStart, int preEnd, int inStart, int inEnd) {
        if (preEnd < preStart) {
            return null;
        }
        int val = pre[preStart];
        int index = map.get(val);
        TreeNode node = new TreeNode(val);
        int sub = index - inStart;
        node.left = buildTree(preStart + 1, preStart + sub,
                              inStart, index - 1);
        node.right = buildTree(preStart + sub + 1, preEnd, index + 1,
                               inEnd);
        return node;

    }
}