PTA数据结构实战：层次遍历巧解二叉树叶结点输出-洪萨配资

1. 从问题理解到解题思路

第一次看到PTA上这道二叉树题目时，我也被题目描述唬住了。题目要求按从上到下、从左到右的顺序输出所有叶结点，这不就是典型的层次遍历（BFS）应用场景吗？但仔细分析输入格式后，我发现有几个关键点需要注意：

输入格式中，每个结点的左右孩子是用字符'-'表示的，这意味着我们需要处理字符到数字的转换。另外，题目给出的结点编号是从0开始的连续整数，这提示我们可以用静态数组来存储树结构，既节省空间又方便查找。

在实际解题时，我总结出三个关键步骤：

从输入数据中找到根节点
根据输入数据构建二叉树
使用层次遍历找出所有叶结点

这种分步解决的方法，把一个大问题拆解成几个小问题，每个小问题都有明确的解决思路，大大降低了编码难度。这也是我在数据结构学习中总结出的重要经验——化整为零，逐个击破。

2. 静态数组存储与根节点查找技巧

在处理树的输入数据时，我发现一个很实用的技巧：用标记数组找根节点。因为除了根节点外，其他所有节点都会作为某个节点的孩子出现。基于这个观察，我们可以创建一个长度为N的标记数组，初始值全为0。

具体实现时，我遍历每个节点的左右孩子，如果孩子存在（不是'-'），就把对应下标的标记数组位置设为1。最后，标记数组中仍为0的位置就是根节点的编号。这个方法的时间复杂度是O(N)，非常高效。

int FindHead(ThreeArr TArr[], int n) { if (n == 1) return 0; int Arr[n]; for(int i = 0; i < n; i++) { Arr[i] = 0; } for(int i = 0; i < n; i++) { if(TArr[i].LNode != '-') { Arr[TArr[i].LNode-'0'] = 1; } if(TArr[i].RNode != '-') { Arr[TArr[i].RNode-'0'] = 1; } } for(int i = 0; i < n; i++) { if(Arr[i] == 0) { return i; } } return -1; // 理论上不会执行到这里 }

这里有个细节需要注意：字符'0'到'9'的ASCII码是连续的，所以可以用child-'0'的方式将字符转换为数字。这个小技巧在处理字符型数字输入时非常实用。

3. 递归构建二叉树

找到根节点后，接下来就是构建二叉树。我采用了递归方法，因为递归的思路最符合树结构的本质特性。每个节点的构建过程都是相同的：创建节点，然后递归创建其左右子树。

TreeNode *BuildTree(int head, ThreeArr TArr[]) { TreeNode *T = (TreeNode *)malloc(sizeof(TreeNode)); T->val = head; T->right = T->left = NULL; if(TArr[head].LNode != '-') T->left = BuildTree(TArr[head].LNode - '0', TArr); if(TArr[head].RNode != '-') T->right = BuildTree(TArr[head].RNode - '0', TArr); return T; }

在实际编码时，我犯过一个错误：忘记处理孩子为'-'的情况，导致程序访问非法内存。这个教训让我明白，边界条件的检查在树结构操作中尤为重要。递归虽然简洁，但必须确保有明确的终止条件，否则很容易导致栈溢出。

4. 层次遍历实现与叶结点判断

题目要求按从上到下、从左到右的顺序输出叶结点，这正是**层次遍历（BFS）**的典型应用。与深度优先搜索（DFS）不同，BFS需要使用队列来辅助实现。

我的实现思路是：

将根节点入队
循环直到队列为空：
- 出队一个节点
- 检查是否是叶结点（左右孩子都为空）
- 将非空左右孩子入队

void LevelOrder(TreeNode *T) { int flag = 0; if(T) { TreeNode *queue[100]; int left = 0, right = 0; queue[right++] = T; while (left < right) { TreeNode *bt = queue[left++]; if(bt->left == NULL && bt->right == NULL) { if(flag == 0) { printf("%d", bt->val); flag++; } else { printf(" %d", bt->val); } } if(bt->left) queue[right++] = bt->left; if(bt->right) queue[right++] = bt->right; } } }

这里有个输出格式的小技巧：使用flag变量控制空格的输出，确保第一个数字前和最后一个数字后没有多余空格。这种细节处理在PTA等在线评测系统中非常重要，可能决定你的代码是否能通过所有测试用例。

5. 完整代码实现与测试

将上述各个部分组合起来，就得到了完整的解决方案。为了验证代码的正确性，我用题目给出的样例进行了测试：

输入：

8 1 - - - 0 - 2 7 - - - - 5 - 4 6

输出：

4 1 5

这个结果与题目给出的样例输出一致，说明我们的实现是正确的。完整的代码如下：

#include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct ThreeArr { char LNode; char RNode; } ThreeArr; int FindHead(ThreeArr TArr[], int n) { if (n == 1) return 0; int Arr[n]; for(int i = 0; i < n; i++) { Arr[i] = 0; } for(int i = 0; i < n; i++) { if(TArr[i].LNode != '-') { Arr[TArr[i].LNode-'0'] = 1; } if(TArr[i].RNode != '-') { Arr[TArr[i].RNode-'0'] = 1; } } for(int i = 0; i < n; i++) { if(Arr[i] == 0) { return i; } } return -1; } TreeNode *BuildTree(int head, ThreeArr TArr[]) { TreeNode *T = (TreeNode *)malloc(sizeof(TreeNode)); T->val = head; T->right = T->left = NULL; if(TArr[head].LNode != '-') T->left = BuildTree(TArr[head].LNode - '0', TArr); if(TArr[head].RNode != '-') T->right = BuildTree(TArr[head].RNode - '0', TArr); return T; } void LevelOrder(TreeNode *T) { int flag = 0; if(T) { TreeNode *queue[100]; int left = 0, right = 0; queue[right++] = T; while (left < right) { TreeNode *bt = queue[left++]; if(bt->left == NULL && bt->right == NULL) { if(flag == 0) { printf("%d", bt->val); flag++; } else { printf(" %d", bt->val); } } if(bt->left) queue[right++] = bt->left; if(bt->right) queue[right++] = bt->right; } } } int main() { int n; scanf("%d", &n); getchar(); ThreeArr ta[n]; for(int i = 0; i < n; i++) { scanf("%c %c", &ta[i].LNode, &ta[i].RNode); getchar(); } int head = FindHead(ta, n); TreeNode *Tree = BuildTree(head, ta); LevelOrder(Tree); return 0; }

在实际编码过程中，我发现有几个常见错误需要注意：