EC19-满二叉树的先序后序互转换¶

代码实现¶

将满二叉树的先序序列转换为后序序列¶

C
// 函数 preTopost：将满二叉树的先序序列转换为后序序列
// 参数：
// pre[]  - 存储先序序列的数组
// L1,R1  - 先序序列的左右边界索引
// post[] - 存储后序序列的数组  
// L2,R2  - 后序序列的左右边界索引
void preTopost(char pre[], int L1, int R1, char post[], int L2, int R2) {
    // 递归终止条件：如果左边界大于右边界，说明子树为空
    if (L1 <= R1) {
        // 先序序列的第一个元素是根节点，在后序序列中应放在最后位置
        post[R2] = pre[L1];

        // 递归处理左子树
        // 先序序列左子树范围：[L1+1, (L1+R1+1)/2]
        // 后序序列左子树范围：[L2, (L2+R2-1)/2]
        preTopost(pre, L1 + 1, (L1 + R1 + 1)/2, post, L2, (L2 + R2 - 1)/2);

        // 递归处理右子树
        // 先序序列右子树范围：[(L1+R1+1)/2+1, R1]
        // 后序序列右子树范围：[(L2+R2-1)/2+1, R2-1]
        preTopost(pre, (L1 + R1 + 1)/2 + 1, R1, post, (L2 + R2 - 1)/2 + 1, R2 - 1);
    }
}

将满二叉树的后序序列转换为先序序列¶

C
// 函数 postTopre：将满二叉树的后序序列转换为先序序列
// 参数含义与上面类似
void postTopre(char post[], int L1, int R1, char pre[], int L2, int R2) {
    // 递归终止条件：如果左边界大于右边界，说明子树为空
    if (L1 <= R1) {
        // 后序序列的最后一个元素是根节点，在先序序列中应放在最前位置
        pre[L2] = post[R1];

        // 特殊情况处理：如果只有一个节点，直接返回
        if (L1 == R1)
            return;

        // 递归处理左子树
        // 后序序列左子树范围：[L1, (L1+R1-1)/2]
        // 先序序列左子树范围：[L2+1, (L2+R2+1)/2]
        postTopre(post, L1, (L1 + R1 - 1)/2, pre, L2 + 1, (L2 + R2 + 1)/2);

        // 递归处理右子树
        // 后序序列右子树范围：[(L1+R1-1)/2+1, R1-1]
        // 先序序列右子树范围：[(L2+R2+1)/2+1, R2]
        postTopre(post, (L1 + R1 - 1)/2 + 1, R1 - 1, pre, (L2 + R2 + 1)/2 + 1, R2);
    }
}

代码逻辑解析¶

1. 满二叉树的性质¶

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点的二叉树
第 k 层有 2^(k-1) 个节点
深度为 h 的满二叉树共有 2^h - 1 个节点

2. 遍历序列的特点¶

先序遍历：根 → 左子树 → 右子树
后序遍历：左子树 → 右子树 → 根

3. 转换核心思想¶

利用满二叉树的结构性质，可以准确计算左右子树的节点数量和边界位置
通过递归分别处理左右子树

关键算法理解¶

1. 边界计算公式的推导¶

先序转后序中的边界计算：¶

C
// 左子树边界计算
// 先序序列左子树范围：[L1+1, (L1+R1+1)/2]
// 后序序列左子树范围：[L2, (L2+R2-1)/2]

推导过程：¶

设当前子树节点总数为 n = R1 - L1 + 1
满二叉树的左子树节点数为 (n-1)/2
右子树节点数也为 (n-1)/2
根节点占1个位置

2. 图解说明¶

假设满二叉树结构：

Text Only
1 2 3 4 5	`A // 根节点 / \ B C // 第1层 / \ / \ D E F G // 第2层`

对应的遍历序列：

Text Only
1 2	`先序序列：[A, B, D, E, C, F, G] // 根-左-右后序序列：[D, E, B, F, G, C, A] // 左-右-根`

转换过程：

Text Only
1 2 3 4 5 6 7 8 9	`pre: [A, B, D, E, C, F, G] 0 1 2 3 4 5 6 ↑ ←----→ ←----→ root left right post: [D, E, B, F, G, C, A] 0 1 2 3 4 5 6 ←----→ ←----→ ↑ left right root`

时间复杂度分析¶

1. 递归次数¶

每个节点被处理 exactly 一次
总共处理 n 个节点

2. 每次递归的操作¶

常数时间的赋值操作：O(1)
常数时间的边界计算：O(1)

3. 总时间复杂度¶

O(n)，其中 n 是节点总数

空间复杂度分析¶

1. 额外空间使用¶

只使用了常量级别的局部变量
没有使用额外的数据结构

2. 递归调用栈空间¶

递归深度为树的高度 h = log₂(n+1)
每次递归调用占用常量栈空间

3. 总空间复杂度¶

O(log n)，即树的高度

边界计算详解¶

1. 先序转后序的边界公式¶

Text Only

当前先序序列范围：[L1, R1]
当前后序序列范围：[L2, R2]

左子树：
- 先序范围：[L1+1, (L1+R1+1)/2]
- 后序范围：[L2, (L2+R2-1)/2]

右子树：
- 先序范围：[(L1+R1+1)/2+1, R1]
- 后序范围：[(L2+R2-1)/2+1, R2-1]

2. 后序转先序的边界公式¶

Text Only

当前后序序列范围：[L1, R1]
当前先序序列范围：[L2, R2]

左子树：
- 后序范围：[L1, (L1+R1-1)/2]
- 先序范围：[L2+1, (L2+R2+1)/2]

右子树：
- 后序范围：[(L1+R1-1)/2+1, R1-1]
- 先序范围：[(L2+R2+1)/2+1, R2]

延伸知识点¶

1. 中序序列的重要性¶

单纯的先序或后序序列无法唯一确定二叉树结构
需要结合中序序列才能唯一确定二叉树

2. 三种遍历序列的相互转换¶

C
// 先序+中序 → 后序
void preInToPost(char pre[], char in[], int preL, int preR, 
                 int inL, int inR, char post[], int postR) {
    if (preL > preR) return;

    post[postR] = pre[preL]; // 根节点

    // 在中序序列中找到根节点位置
    int rootIndex = findRoot(in, pre[preL], inL, inR);

    int leftSize = rootIndex - inL; // 左子树节点数

    // 递归处理左子树
    preInToPost(pre, in, preL+1, preL+leftSize,
                inL, rootIndex-1, post, postR-leftSize-1);

    // 递归处理右子树
    preInToPost(pre, in, preL+leftSize+1, preR,
                rootIndex+1, inR, post, postR-1);
}

3. 满二叉树的其他性质¶

第 i 层最多有 2^(i-1) 个节点
深度为 k 的满二叉树总共有 2^k - 1 个节点
叶子节点数 = (n+1)/2，其中 n 为总节点数
度为2的节点数 = (n-1)/2

4. 实际应用¶

表达式树：编译器中用于表示算术表达式
哈夫曼树：数据压缩算法中使用
决策树：机器学习中的分类算法
语法分析树：编译原理中的语法分析

5. 优化建议¶

C
// 迭代版本 - 使用栈模拟递归
void preToPostIterative(char pre[], int n, char post[]) {
    // 使用栈存储边界信息
    Stack* stack = createStack();
    push(stack, 0); push(stack, n-1);  // pre边界
    push(stack, 0); push(stack, n-1);  // post边界

    while (!isEmpty(stack)) {
        int R2 = pop(stack);
        int L2 = pop(stack);
        int R1 = pop(stack);
        int L1 = pop(stack);

        if (L1 <= R1) {
            post[R2] = pre[L1];

            // 计算中间点
            int mid1 = (L1 + R1 + 1) / 2;
            int mid2 = (L2 + R2 - 1) / 2;

            // 右子树先入栈（后处理）
            push(stack, mid1 + 1); push(stack, R1);
            push(stack, mid2 + 1); push(stack, R2 - 1);

            // 左子树后入栈（先处理）
            push(stack, L1 + 1); push(stack, mid1);
            push(stack, L2); push(stack, mid2);
        }
    }
}

这些算法体现了分治思想和递归思维，是数据结构与算法中的经典问题。