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

BraumAce2024年8月11日约 866 字大约 3 分钟

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

思路

前序遍历性质：节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

根据以上性质，可得出以下推论：

前序遍历的首元素为树的根节点 node 的值。
在中序遍历中搜索根节点 node 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ]。
根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ]。

如下图:

通过以上三步，可确定三个节点：1.树的根节点、2.左子树根节点、3.右子树根节点。

根据分治思想，对于树的左、右子树，仍可复用以上方法划分子树的左右子树。

递归建树:

先建立根节点：从前序遍历数组的第一个元素开始，根节点为 preorder[0]
再划分左右子树：确定根节点再中序遍历中的位置 i，划分左子树范围 [left, i - 1]，右子树范围 [i + 1, right]
最后构建左右子树：开始左右子树递归

设前序遍历中根节点的索引为 root，则左子节点索引为 root + 1，右子节点索引为 root + i - left + 1.

由于是根据前序遍历的节点来确定中序遍历中节点的位置，所以使用 Map 存储中序遍历的节点与索引的映射关系。

注意

本文方法只适用于 “无重复节点值” 的二叉树。

如果题目中给定的节点值存在重复的解法：https://doocs.github.io/leetcode/lc/105/#_3

代码

class Solution {
    int[] preorder;
    HashMap<Integer, Integer> mp = new HashMap<>();

    TreeNode build(int root, int left, int right) {
        if (left > right) return null;                          // 递归终止
        
        TreeNode node = new TreeNode(preorder[root]);          // 建立根节点
        int i = mp.get(preorder[root]);                       // 划分根节点、左子树、右子树
        node.left = build(root + 1, left, i - 1);              // 开启左子树递归
        node.right = build(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;                                           // 回溯返回根节点
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for(int i = 0; i < inorder.length; i++){
            mp.put(inorder[i], i);
        }

        return build(0, 0, inorder.length - 1);
    }
}

另外一种 K 神的写法：

class Solution {
    // map存节点和对应的下标
    Map<Integer, Integer> premap = new HashMap<>();  // 前序
    Map<Integer, Integer> inmap = new HashMap<>();  // 中序

    // 当left = right时返回
    TreeNode build(int rootIndex, int left, int right, int[] preorder, int[] inorder) {
        if (left > right) return null;
        if (left == right) return new TreeNode(inorder[left]);

        int rootPreIndex = premap.get(rootIndex);
        int rootInIndex = inmap.get(rootIndex);
        TreeNode root = new TreeNode(rootIndex);
        // 建立左子树
        if (rootPreIndex + 1 > 0 && rootPreIndex < preorder.length){
            root.left = build(preorder[rootPreIndex + 1], left, rootInIndex - 1, preorder, inorder);
        } else {
            root.left = null;
        }
        // 建立右子树
        if (rootPreIndex + rootInIndex - left + 1 > 0 && rootPreIndex + rootInIndex - left + 1 < preorder.length){
            root.right = build(preorder[rootPreIndex + rootInIndex - left + 1], rootInIndex + 1, right, preorder, inorder);
        } else {
            root.right = null;
        }

        // 返回根节点
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < preorder.length; i++){
            premap.put(preorder[i], i);
        }
        for (int i = 0; i < inorder.length; i++){
            inmap.put(inorder[i], i);
        }

        return build(preorder[0], 0, preorder.length - 1, preorder, inorder);
    }
}

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

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

题意

思路

代码