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

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 inOrder int整型一维数组
     * @return TreeNode类
     */
    private Map<Integer, Integer> pos;

    /**
     * 根据前序遍历和中序遍历构建二叉树
     *
     * @param preOrder 前序遍历结果数组
     * @param preLeft  前序遍历结果的左边界
     * @param preRight 前序遍历结果的右边界
     * @param inLeft   中序遍历结果的左边界
     * @return 构建好的二叉树的根节点
     */
    public TreeNode buildTree(int[] preOrder, int preLeft, int preRight,
                              int inLeft) {
        if (preLeft > preRight) return null;

        // 根据根节点值在中序遍历结果中找到根节点的位置
        int inRoot = pos.get(preOrder[preLeft]);

        // 创建根节点
        TreeNode root = new TreeNode(preOrder[preLeft]);

        // 计算左子树的大小
        int leftSubtreeSize = inRoot - inLeft;

        // 递归构建左子树和右子树
        root.left = buildTree(preOrder, preLeft + 1, preLeft + leftSubtreeSize, inLeft);
        root.right = buildTree(preOrder, preLeft + leftSubtreeSize + 1, preRight,
                               inRoot + 1);

        return root;
    }

    /**
     * 根据前序遍历和中序遍历构建二叉树
     *
     * @param preOrder 前序遍历结果数组
     * @param inOrder  中序遍历结果数组
     * @return 构建好的二叉树的根节点
     */
    public TreeNode buildTreeII(int[] preOrder, int[] inOrder) {
        pos = new HashMap<>();

        // 构建中序遍历结果中值到索引的映射，加快查找根节点位置的速度
        for (int i = 0; i < inOrder.length; ++i) {
            pos.put(inOrder[i], i);
        }

        // 调用递归函数构建二叉树
        return buildTree(preOrder, 0, preOrder.length - 1, 0);
    }
}

该代码使用的编程语言是Java。

此代码考察了以下知识点：

1. 二叉树的构建和遍历：根据给定的前序遍历和中序遍历结果，构建二叉树。
2. 递归：通过递归的方式构建二叉树，每次处理左子树和右子树。
3. 哈希表（HashMap）的使用：为了加快查找根节点位置的速度，将中序遍历结果中的元素及其对应的索引存储在哈希表中。

代码的文字解释大纲如下：

1. 构建了一个树节点类 TreeNode，表示二叉树的节点。
2. 创建了一个 Solution 类，包含了构建二叉树的方法 buildTree 和 buildTreeII。
3. buildTree 方法根据给定的前序遍历和中序遍历结果构建二叉树。方法中传入了前序遍历结果数组、前序遍历结果的左边界和右边界以及中序遍历结果的左边界。首先判断边界情况，如果左边界大于右边界，则返回空节点。在中序遍历结果中找到根节点的位置（通过哈希表加快查找速度）。创建根节点，并递归构建左子树和右子树。返回构建好的二叉树的根节点。
4. buildTreeII 方法是对外公开的方法，用于调用 buildTree 方法构建二叉树。方法中传入了前序遍历结果数组和中序遍历结果数组。创建一个哈希表，存储中序遍历结果中的元素及其在数组中的索引。调用 buildTree 方法构建二叉树，并返回根节点。