小学生都能看懂的题解 | #重建二叉树#

想象一下你在玩拼图游戏，现在有两组数字卡片，一组叫“前序卡片”，另一组叫“中序卡片”。我们要用这两组卡片来重建一棵树形的图案。

步骤分解：

1. 前序卡片：
1. 它告诉我们树是怎么开始生长的。比如，第一个数字代表了树的根。
2. 中序卡片：
1. 它告诉我们树上的数字是如何排列的。
2. 比如，如果树是从左到右画出来的，那么中序卡片就告诉了我们这些数字从左到右的顺序。

举例：

假设前序卡片是 [1, 2, 4, 7, 3, 5, 6, 8]，中序卡片是 [4, 7, 2, 1, 5, 3, 8, 6]。

• 首先，我们看到前序卡片的第一个数字是 1，这意味着 1 是树的根。
• 接着，在中序卡片中找到 1，它在这里的位置是第四个（从0开始数）。
• 在 1 的左边，也就是 [4, 7, 2]，这部分代表了根节点 1 的左子树。
• 在 1 的右边，也就是 [5, 3, 8, 6]，这部分代表了根节点 1 的右子树。

如何一步步来：

1. 找到根：
1. 前序的第一个数字 1 是根。
2. 找到左子树：
1. 在中序卡片中找到根 1，它左边的所有数字 [4, 7, 2] 构成了左子树。
3. 找到右子树：
1. 同样在中序卡片中找到根 1，它右边的所有数字 [5, 3, 8, 6] 构成了右子树。
4. 重复以上步骤：
1. 对于左子树 [4, 7, 2] 和右子树 [5, 3, 8, 6]，分别用前序卡片中的相应部分和中序卡片中的相应部分，重复上面的步骤来构建子树。

就这样一步步地，我们就可以用这两组数字卡片来重建出整个树形图案啦！

下面是简单的代码实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Solution {
    // 使用HashMap来存储中序遍历中每个值的索引
    HashMap<Integer, Integer> map = new HashMap<>();
    
    public TreeNode reConstructBinaryTree(int[] preOrder, int[] vinOrder) {
        // 初始化HashMap
        for (int i = 0; i < vinOrder.length; i++) {
            map.put(vinOrder[i], i);
        }
        // 调用递归函数
        return reConstructBinaryTree(preOrder, 0, preOrder.length - 1, 0, vinOrder.length - 1);
    }
    
    private TreeNode reConstructBinaryTree(int[] preOrder, int preStart, int preEnd, int vinStart, int vinEnd) {
        if (preStart > preEnd) {
            return null;
        }
        
        // 根据前序遍历的第一个元素确定根节点
        TreeNode root = new TreeNode(preOrder[preStart]);
        
        // 在中序遍历中找到根节点的位置
        int vinRootIndex = map.get(preOrder[preStart]);
        
        // 计算左子树的长度
        int leftLength = vinRootIndex - vinStart;
        
        // 递归构建左子树
        root.left = reConstructBinaryTree(preOrder, preStart + 1, preStart + leftLength, vinStart, vinRootIndex - 1);
        
        // 递归构建右子树
        root.right = reConstructBinaryTree(preOrder, preStart + leftLength + 1, preEnd, vinRootIndex + 1, vinEnd);
        
        return root;
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。