中序遍历如何按完全二叉树层次输出？

Question

在二叉树遍历中，中序遍历按“左-根-右”顺序访问节点，天然适用于BST的有序输出。然而，若给定一棵完全二叉树，如何在不重建树结构的前提下，将中序遍历序列重新组织为层次遍历（即按层从上到下、每层从左到右）的输出？常见问题是：已知完全二叉树的中序遍历结果，如何通过索引映射或队列辅助，还原其层次遍历序列？难点在于中序遍历不直接反映层级关系，需结合完全二叉树的结构性质（如数组表示下的父子节点索引规律）进行逆向推导。

Answer 1

从完全二叉树的中序遍历还原层次遍历：由浅入深的技术解析

1. 问题背景与核心概念梳理

在二叉树的遍历体系中，中序遍历（In-order Traversal）遵循“左-根-右”的访问顺序，这一特性使其天然适用于二叉搜索树（BST），能够输出有序序列。然而，当面对的是完全二叉树（Complete Binary Tree）时，我们常需解决一个逆向问题：

• 已知一棵完全二叉树的中序遍历序列；
• 目标是不重建树结构的前提下，直接还原其层次遍历（Level-order Traversal）结果。

这个问题的挑战在于：中序遍历本身不体现层级信息，而层次遍历则严格依赖节点在树中的位置关系。因此，必须借助完全二叉树的结构性质进行索引映射和逻辑推导。

2. 完全二叉树的结构特性回顾

完全二叉树具有如下关键性质，这些性质为后续算法设计提供了理论基础：

1. 除最后一层外，其余层全部填满；
2. 最后一层节点尽可能靠左排列；
3. 可用数组表示，节点索引从0开始，则对于任意节点i：
4. • 左子节点索引为 2*i + 1；
   • 右子节点索引为 2*i + 2；
   • 父节点索引为 Math.floor((i-1)/2)。

该数组表示法使得我们可以仅通过索引运算模拟树结构行为，无需显式构建TreeNode对象。

3. 中序遍历在数组中的分布规律分析

考虑一个n个节点的完全二叉树，若将其按层次存储在数组A[0..n-1]中，则其中序遍历序列并非简单地等于A的某种重排。但可以证明：中序遍历的访问顺序对应于一种中序索引映射函数。

树节点数n	中序访问序列（索引）	层次遍历索引
7	[3,1,4,0,5,2,6]	[0,1,2,3,4,5,6]
3	[1,0,2]	[0,1,2]
1	[0]	[0]
15	[7,3,8,1,9,4,10,0,11,5,12,2,13,6,14]	[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14]

观察可知，中序遍历的根节点总是出现在中间位置附近，具体取决于子树大小。这提示我们可通过递归划分区间来定位每层节点。

4. 解决方案一：基于中序索引重建层次顺序

核心思想是利用完全二叉树的形态确定每个子树的中序区间，并将根节点依次填入结果数组的正确位置。

function inorderToLevelOrder(inorder) {
    const n = inorder.length;
    const levelOrder = new Array(n);
    
    function buildIndex(low, high, index) {
        if (low > high) return;
        const size = high - low + 1;
        const leftSize = Math.pow(2, Math.floor(Math.log2(size + 1))) - 1;
        const actualLeft = Math.min(leftSize, Math.ceil((size - 1) / 2));
        const rootIndexInOrder = low + actualLeft;

        levelOrder[index] = inorder[rootIndexInOrder];

        buildIndex(low, rootIndexInOrder - 1, 2 * index + 1);
        buildIndex(rootIndexInOrder + 1, high, 2 * index + 2);
    }

    buildIndex(0, n - 1, 0);
    return levelOrder;
}

上述代码通过计算左子树规模，定位中序序列中的根节点，并将其映射到层次数组的指定索引处。

5. 解决方案二：队列辅助的广度优先重构策略

另一种思路是使用队列模拟层次遍历过程，在每一步决定当前应填充哪个中序区间的“根”元素。

graph TD A[初始化队列，入队根区间[0,n-1]] --> B{出队区间[low,high]} B --> C[计算左子树大小] C --> D[确定中序根位置: rootPos = low + leftSize] D --> E[将inorder[rootPos]填入levelOrder对应位置] E --> F[左子区间入队: [low, rootPos-1]] E --> G[右子区间入队: [rootPos+1, high]] F --> H{队列非空?} G --> H H -- 是 --> B H -- 否 --> I[完成层次序列构造]

此方法避免了递归调用栈，更适合大规模数据处理场景。

6. 复杂度分析与工程优化建议

两种方案的时间复杂度均为O(n)，因每个节点仅被处理一次；空间复杂度为O(log n)（递归深度或队列长度）。但在实际系统中，可进一步优化：

• 预计算所有子树规模表，减少重复对数运算；
• 使用位运算替代Math.pow和Math.log2提升性能；
• 结合缓存机制处理高频查询场景。

此外，该技术可扩展至堆结构分析、序列化协议逆向等领域。