L2-3 完全二叉树的层序遍历分数--天梯赛题解

loopdeloop

于 2025-04-09 22:36:07 发布

阅读量316

点赞数 5

文章标签：数据结构算法

本文链接：https://blog.csdn.net/loopdeloop/article/details/147104468

版权

L2-3 完全二叉树的层序遍历

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为 D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前 N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入格式：

输入在第一行中给出正整数 N（≤30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100 的正整数。同一行中所有数字都以空格分隔。

输出格式：

在一行中输出该树的层序遍历序列。所有数字都以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

8
91 71 2 34 10 15 55 18

输出样例：

18 34 55 71 2 10 15 91

解题思路

完全二叉树的性质：
- 完全二叉树可以使用数组来表示，其中对于节点i，其左孩子是2i，右孩子是2i+1
- 这种表示方法使得层序遍历就是数组的顺序遍历
后序遍历重建：
- 后序遍历的顺序是：左子树 → 右子树 → 根节点
- 我们可以利用递归的方式，按照后序的顺序填充完全二叉树的节点值
层序遍历输出：
- 由于完全二叉树使用数组表示，层序遍历就是数组从1到N的顺序输出

代码实现

#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    int left;
    int right;
} tree[35]; // 最多30个节点，数组大小设为35

int n;

// 后序遍历填充完全二叉树
void postOrder(int index) {
    if (index > n) return;
    
    // 递归处理左子树
    if (tree[index].left) 
        postOrder(tree[index].left);
    
    // 递归处理右子树
    if (tree[index].right) 
        postOrder(tree[index].right);
    
    // 读取当前节点的值
    cin >> tree[index].val;
}

int main() {
    cin >> n;
    
    // 构建完全二叉树的结构
    for (int i = 1; i <= n; i++) {
        if (2 * i <= n) 
            tree[i].left = 2 * i;
        if (2 * i + 1 <= n) 
            tree[i].right = 2 * i + 1;
    }
    
    // 后序遍历填充节点值
    postOrder(1);
    
    // 输出层序遍历结果（即数组顺序）
    cout << tree[1].val;
    for (int i = 2; i <= n; i++) {
        cout << " " << tree[i].val;
    }
    
    return 0;
}