N叉树的三种遍历(层次遍历、前序遍历、后序遍历)

N叉树是一种特殊的树形结构，它的每个节点可以拥有多个子节点。在对N叉树进行遍历时，有三种常用的遍历方式：层次遍历、前序遍历和后序遍历。

层次遍历

层次遍历是一种逐层遍历整棵N叉树的方法，它是通过队列实现的。可以采用BFS算法（广度优先遍历）将每一层的节点先全部入队列，然后依次出队列并输出。

示例1：

对于如下的一棵简单的N叉树，进行层次遍历：

    1
   /|\ \
  2 3  4 5

层次遍历的输出应该是 1 2 3 4 5。

示例2：

对于如下的一棵稍微复杂一些的 4 叉 N 叉树，进行层次遍历：

        1
   / / | \ \
  2 3  4  5 6
 / \    |   /
7   8   9 10

层次遍历的输出应该是 1 2 3 4 5 6 7 8 9 10。

具体实现见下文代码块。

前序遍历

前序遍历的方式是遍历整棵N叉树的节点，并将节点的值依次输出。遍历顺序为根节点 -> 左子树 -> 右子树。

示例3：

对于如下一棵 N 叉树，进行前序遍历：

      1
    / | \
   3  2  4
  / \
 5   6

前序遍历的输出应该是 1 3 5 6 2 4。

具体实现见下文代码块。

后序遍历

后序遍历是深度优先遍历 N 叉树的一种策略，遍历顺序为左子树 -> 右子树 -> 根节点。

示例4：

对于如下的一棵 N 叉树，进行后序遍历：

      1
   / / \ \
  2 3  4  5
    |     |
    6     7

后序遍历的输出应该是 2 6 3 4 7 5 1。

具体实现见下文代码块。

示例代码

"""
定义 N 叉树的类 Node 和遍历的函数，包括层次遍历，前序遍历和后序遍历。
"""

class Node():
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

def levelOrder(root):
    """
    层次遍历函数，使用队列实现。
    """
    if not root:
        return []
    res, queue = [], [root]
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            queue.extend(node.children)
        res.append(level)
    return res

def preorder(root):
    """
    前序遍历函数，使用递归实现。
    """
    def dfs(node):
        nonlocal res
        if not node:
            return
        res.append(node.val)
        for child in node.children:
            dfs(child)
    res = []
    dfs(root)
    return res

def postorder(root):
    """
    后序遍历函数，使用递归实现。
    """
    def dfs(node):
        nonlocal res
        if not node:
            return
        for child in node.children:
            dfs(child)
        res.append(node.val)
    res = []
    dfs(root)
    return res

# 示例1
node5 = Node(5)
node4 = Node(4)
node3 = Node(3)
node2 = Node(2)
root = Node(1, [node2, node3, node4, node5])
assert levelOrder(root) == [[1], [2, 3, 4], [5]]
assert preorder(root) == [1, 2, 3, 5, 4]
assert postorder(root) == [5, 2, 3, 4, 1]

# 示例2
node10 = Node(10)
node9 = Node(9)
node8 = Node(8)
node7 = Node(7)
node6 = Node(6, [node10])
node5 = Node(5)
node4 = Node(4, [node9])
node3 = Node(3, [node7, node8])
node2 = Node(2, [node5, node6])
root = Node(1, [node2, node3, node4])
node5.children.append(node7)
assert levelOrder(root) == [[1], [2, 3, 4], [5, 6, 7, 8, 9], [10]]
assert preorder(root) == [1, 2, 5, 6, 10, 3, 7, 8, 4, 9]
assert postorder(root) == [10, 6, 5, 7, 8, 3, 9, 4, 1]