题解 | #重建二叉树#

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 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型一维数组 
     * @param vinOrder int整型一维数组 
     * @return TreeNode类
     */
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode reConstructBinaryTree (int[] preOrder, int[] vinOrder) {
        for(int i = 0; i < vinOrder.length; i++) {
            map.put(vinOrder[i], i);
        }

        return build(preOrder, 0, preOrder.length, vinOrder, 0, vinOrder.length);
    }

    // [begin, end)
    TreeNode build(int[] preOrder, int preBegin, int preEnd, 
                    int[] vinOrder, int vinBegin, int vinEnd) {
        if(preBegin >= preEnd || vinBegin >= vinEnd) {
            return null; // 没有节点可以构造了
        }

        int rootVal = preOrder[preBegin];
        int rootIdx = map.get(rootVal);
        int leftTreeLen = rootIdx - vinBegin;
        TreeNode root = new TreeNode(rootVal);
        root.left = build(preOrder, preBegin + 1, preBegin + 1 + leftTreeLen, vinOrder, vinBegin, rootIdx);
        root.right = build(preOrder, preBegin + 1 + leftTreeLen, preEnd, vinOrder, rootIdx + 1, vinEnd);
        return root;
    }
}