105.从前序与中序遍历序列构造二叉树

在这里插入图片描述

// 定义一个名为 Solution 的类
class Solution {

    // 创建一个哈希映射（Map）对象，用于根据数值查找对应的索引位置
    Map<Integer, Integer> map;

    // 公共方法 buildTree，接收两个整数数组（前序遍历序列 preorder 和 中序遍历序列 inorder）作为参数
    // 方法返回根据这两个序列重建后的二叉树的根节点
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        // 初始化哈希映射
        map = new HashMap<>();

        // 遍历中序遍历序列，将每个元素与其索引存入哈希映射中，便于后续查找
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        // 调用辅助方法 findNode 递归构建二叉树
        // 参数传递的是前序遍历与中序遍历序列的起始和结束索引，采用前闭后开区间
        return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    // 辅助方法 findNode，用于递归地构建二叉树
    // 接收前序遍历与中序遍历的起始和结束索引
    public TreeNode findNode(int[] preorder, int preBegin, int preEnd, 
                             int[] inorder, int inBegin, int inEnd) {

        // 如果输入的索引范围不合法（如已超出边界），说明没有元素，返回空树
        if (preBegin >= preEnd || inBegin >= inEnd) {
            return null;
        }

        // 前序遍历的第一个元素是树的根节点，在中序遍历中找到此元素的位置
        int rootIndex = map.get(preorder[preBegin]);

        // 根据中序遍历中找到的位置创建新的 TreeNode（根节点）
        TreeNode root = new TreeNode(inorder[rootIndex]);

        // 计算中序遍历中左子树的元素个数，从而确定前序遍历中左子树的元素范围
        int lenOfLeft = rootIndex - inBegin;

        // 递归构造左子树并将结果赋值给根节点的 left 属性
        root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,
                            inorder, inBegin, rootIndex);

        // 递归构造右子树并将结果赋值给根节点的 right 属性
        root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
                            inorder, rootIndex + 1, inEnd);

        // 返回当前构建好的根节点
        return root;
    }
}