从遍历序列构造二叉树：前序+中序与中序+后序的递归解法详解

进击的小白菜

1098人浏览 · 2025-04-29 18:50:15

进击的小白菜 · 2025-04-29 18:50:15 发布

文章目录

1. 问题背景

二叉树的遍历方式包括前序（根-左-右）、中序（左-根-右）和后序（左-右-根）。给定其中两种遍历序列，能否唯一确定一棵二叉树的结构？

前序+中序：可以唯一确定二叉树。
中序+后序：可以唯一确定二叉树。
前序+后序：无法唯一确定（存在多种可能性）。

本文详细讲解如何通过 前序+中序 和 中序+后序 两种组合构造二叉树。

2. 核心思路

两种问题的解法均基于 递归分治，核心步骤如下：

确定根节点
- 前序序列的第一个元素为根节点。
- 后序序列的最后一个元素为根节点。
分割左右子树
- 利用根节点在中序序列中的位置，将中序序列分割为左子树和右子树。
- 根据中序序列的左右子树长度，确定前序或后序序列的子树区间。
递归构建子树
- 对左子树和右子树重复上述过程，直到无法分割。

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

3.1 递归分治思路

根节点：前序序列的起始元素 preorder[preStart]。
中序分割：根据根节点在中序序列中的位置 rootIndex，分割左子树和右子树。
前序分割：
- 左子树的前序区间：preStart + 1 至 preStart + leftSubtreeSize
- 右子树的前序区间：preStart + leftSubtreeSize + 1 至 preEnd

3.2 代码实现与注释

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 哈希表存储中序序列的值与索引，便于快速查找根节点位置
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(preorder, 0, preorder.length - 1, 
                               inorder, 0, inorder.length - 1, 
                               inorderMap);
    }

    private TreeNode buildTreeHelper(int[] preorder, int preStart, int preEnd, 
                                     int[] inorder, int inStart, int inEnd, 
                                     Map<Integer, Integer> inorderMap) {
        // 终止条件：区间无效时返回null
        if (preStart > preEnd || inStart > inEnd) return null;

        // 根节点为前序序列的起始元素
        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        // 获取根节点在中序序列中的位置
        int rootIndex = inorderMap.get(rootVal);
        int leftSubtreeSize = rootIndex - inStart; // 左子树节点数量

        // 递归构建左子树
        root.left = buildTreeHelper(
            preorder, 
            preStart + 1,                   // 左子树前序起始
            preStart + leftSubtreeSize,     // 左子树前序结束
            inorder, 
            inStart,                        // 左子树中序起始
            rootIndex - 1,                  // 左子树中序结束
            inorderMap
        );

        // 递归构建右子树
        root.right = buildTreeHelper(
            preorder, 
            preStart + leftSubtreeSize + 1, // 右子树前序起始
            preEnd,                         // 右子树前序结束
            inorder, 
            rootIndex + 1,                  // 右子树中序起始
            inEnd,                          // 右子树中序结束
            inorderMap
        );

        return root;
    }
}

4. 从中序与后序遍历序列构造二叉树

4.1 递归分治思路

根节点：后序序列的末尾元素 postorder[postEnd]。
中序分割：根据根节点在中序序列中的位置 rootIndex，分割左子树和右子树。
后序分割：
- 左子树的后序区间：postStart 至 postStart + leftSubtreeSize - 1
- 右子树的后序区间：postStart + leftSubtreeSize 至 postEnd - 1

4.2 代码实现与注释

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // 哈希表存储中序序列的值与索引
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return buildTreeHelper(postorder, 0, postorder.length - 1, 
                               inorder, 0, inorder.length - 1, 
                               inorderMap);
    }

    private TreeNode buildTreeHelper(int[] postorder, int postStart, int postEnd,
                                     int[] inorder, int inStart, int inEnd,
                                     Map<Integer, Integer> inorderMap) {
        // 终止条件：区间无效时返回null
        if (postStart > postEnd || inStart > inEnd) return null;

        // 根节点为后序序列的末尾元素
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);

        // 获取根节点在中序序列中的位置
        int rootIndex = inorderMap.get(rootVal);
        int leftSubtreeSize = rootIndex - inStart; // 左子树节点数量

        // 递归构建左子树
        root.left = buildTreeHelper(
            postorder, 
            postStart,                          // 左子树后序起始
            postStart + leftSubtreeSize - 1,     // 左子树后序结束
            inorder, 
            inStart,                             // 左子树中序起始
            rootIndex - 1,                       // 左子树中序结束
            inorderMap
        );

        // 递归构建右子树
        root.right = buildTreeHelper(
            postorder, 
            postStart + leftSubtreeSize,         // 右子树后序起始
            postEnd - 1,                         // 右子树后序结束（排除根节点）
            inorder, 
            rootIndex + 1,                      // 右子树中序起始
            inEnd,                              // 右子树中序结束
            inorderMap
        );

        return root;
    }
}

5. 复杂度分析

时间复杂度：O(n)
每个节点被访问一次，哈希表查询操作 O(1)。
空间复杂度：O(n)
哈希表存储中序序列 O(n)，递归栈深度在最坏情况下为 O(n)（树退化为链表）。

6. 总结

核心共性
- 通过根节点分割中序序列，确定左右子树的区间。
- 递归处理左右子树时，需精准计算前序或后序序列的子树区间。
关键区别
- 根节点位置：前序序列首元素 vs. 后序序列末元素。
- 区间计算：前序需跳过根节点后分割，后序需排除末元素后分割。
扩展思考
- 如何验证构建的二叉树是否正确？
  重新生成前序/中序/后序遍历序列，与原输入比对。
- 如果遍历序列中存在重复值，上述方法是否有效？
  无效，因为哈希表无法唯一确定根节点位置。