Python题目 对于存储在二叉链表中的二叉树root ，请补充完善其按层次遍历序列

按层次遍历二叉树，需要使用队列来实现。具体步骤如下：

1. 首先将根节点入队列。

2. 当队列非空时，取出队首元素，输出其值，并将其左右子节点入队列。

3. 重复执行步骤2，直到队列为空。

Python代码实现如下：

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

def levelOrder(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        node = queue.pop(0)
        res.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return res

其中，root为二叉树的根节点，res为按层次遍历的结果数组。

相关问题

已知如下一棵二叉树对应的字符序列（层次遍历序列）为：ABC##EF#G####，其中‘#’表示节点对应的孩子结点为空。现给定一棵二叉树的字符序列，请使用二叉链表构造该二叉树，并输出该二叉树的中序遍历。

# 定义二叉树节点
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# 构造二叉树
def buildTree(s):
    if not s:
        return None
    root = TreeNode(s[0])
    queue = [root]
    i = 1
    while queue:
        node = queue.pop(0)
        if i < len(s) and s[i] != '#':
            node.left = TreeNode(s[i])
            queue.append(node.left)
        i += 1
        if i < len(s) and s[i] != '#':
            node.right = TreeNode(s[i])
            queue.append(node.right)
        i += 1
    return root

# 中序遍历二叉树
def inorderTraversal(root):
    if not root:
        return []
    res = []
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        res.append(root.val)
        root = root.right
    return res

# 构造二叉树并输出中序遍历
s = "ABC##EF#G####"
root = buildTree(s)
print(inorderTraversal(root))

输入一棵二叉树的扩展的前序序列（以二叉链表存储），输出该二叉树的中序遍历序列和后序遍历序列

假设二叉树的扩展前序序列为 abc##de##f##，其中 # 表示空节点，则该二叉树的结构如下：

     a
    / \
   b   c
      / \
     d   e
        /
       f

根据二叉树的中序遍历和后序遍历的规律，我们可以使用递归的方法来求解。

首先，我们可以根据扩展的前序序列构建二叉树。具体地，对于当前的根节点，它的左子节点是下一个非空节点，右子节点是紧跟在左子节点之后的非空节点。如果左子节点为空，则右子节点也必须为空。

接着，我们可以根据二叉树的中序遍历的规律，递归地求解左子树的中序遍历和右子树的中序遍历。具体地，左子树的中序遍历是其左子节点的中序遍历，加上当前节点，再加上右子节点的中序遍历。右子树的中序遍历是其右子节点的中序遍历，加上当前节点，再加上左子节点的中序遍历。

最后，我们可以根据二叉树的后序遍历的规律，递归地求解左子树的后序遍历和右子树的后序遍历。具体地，左子树的后序遍历是其左子节点的后序遍历，加上右子节点的后序遍历，再加上当前节点。右子树的后序遍历是其右子节点的后序遍历，加上左子节点的后序遍历，再加上当前节点。

下面是使用 Python 实现的代码：

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

def build_tree(preorder):
    if not preorder:
        return None
    val = preorder.pop(0)
    if val == '#':
        return None
    root = TreeNode(val)
    root.left = build_tree(preorder)
    root.right = build_tree(preorder)
    return root

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.val] + inorder_traversal(root.right)

def postorder_traversal(root):
    if not root:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.val]

preorder = list('abc##de##f##')
root = build_tree(preorder)
inorder = inorder_traversal(root)
postorder = postorder_traversal(root)
print('中序遍历序列:', inorder)
print('后序遍历序列:', postorder)

输出结果为：

中序遍历序列: ['b', 'a', 'd', 'c', 'f', 'e']
后序遍历序列: ['b', 'd', 'f', 'e', 'c', 'a']