pta7-1 玩转二叉树

### PTA 7-1 二叉树题目解析

#### 题目描述
给定一棵二叉树的完全前序序列，构建该二叉树并输出其层次遍历结果。假设二叉树的数据元素为单个字符且各不相同，取值范围为 A~Z 和 a~z，二叉树不为空。输入数据分为两行，第一行为二叉树完全前序序列字符（包括 `#`）个数，第二行为二叉树的完全前序序列。例如，上述二叉树的输入为：`ABD##FE###CG#H##I##`，其中 `#` 表示空位置。

#### 输入格式
- 第一行是一个整数 N (N ≤ 50)，表示完全前序序列中的字符总数。
- 第二行是长度为 N 的字符串 S，表示二叉树的完全前序序列。

#### 输出格式
按照层次遍历顺序输出二叉树节点的字符，每两个字符之间用一个空格隔开。

#### 解决方案
为了实现这一功能，可以采用递归方法来重建二叉树，并通过队列来进行层次遍历。以下是具体的 Python 实现：

class TreeNode:
    def __init__(self, val=None):
        self.val = val
        self.left = None
        self.right = None


def build_tree(preorder):
    if not preorder or preorder[0] == '#':
        return None
    
    root_val = preorder.pop(0)
    node = TreeNode(root_val)

    node.left = build_tree(preorder)
    node.right = build_tree(preorder)

    return node


def level_order_traversal(root):
    result = []
    queue = [root]

    while queue:
        current_node = queue.pop(0)
        if current_node is not None:
            result.append(current_node.val)
            queue.extend([current_node.left, current_node.right])
    
    return ' '.join(result)


if __name__ == "__main__":
    n = int(input().strip())
    s = list(input().strip())

    tree_root = build_tree(s)
    print(level_order_traversal(tree_root))

此代码片段展示了如何基于给定的前序序列创建二叉树以及执行层次遍历操作[^1]。