Python实现非二叉树从左到右inorder中序遍历生成值列表

首先明确非二叉树（多叉树）的中序遍历规则——由于多叉树没有二叉树明确的左右子节点划分，通用的从左到右中序遍历规则为：

对任意节点：

• 无任何子节点（叶子节点）：直接读取节点值
• 存在k个子节点（k≥1）：
  1. 按从左到右顺序递归遍历前k-1棵子树
  2. 读取当前节点值
  3. 递归遍历最右侧的第k棵子树

我们默认传入的多叉树节点遵循通用结构定义：

class Node:
    def __init__(self, val=None, children=None):
        self.val = val  # 节点存储的取值
        self.children = children if children is not None else []  # 从左到右排列的子节点列表

递归实现（逻辑直观，适合树深度不大的场景） #

def nary_inorder_traversal(root: Node) -> list:
    result = []

    def dfs(node):
        if not node:
            return
        child_num = len(node.children)
        # 遍历前n-1棵左端子树
        for idx in range(child_num - 1):
            dfs(node.children[idx])
        # 读取当前节点值
        result.append(node.val)
        # 遍历最右端子树
        if child_num > 0:
            dfs(node.children[-1])

    dfs(root)
    return result

迭代实现（手动维护栈，避免递归深度溢出） #

如果树的深度很大，递归可能触发Python默认递归深度限制报错，可以用栈手动模拟遍历过程：

def nary_inorder_traversal_iter(root: Node) -> list:
    if not root:
        return []
    result = []
    # 栈存储格式为(节点, 是否已处理过子节点)
    stack = [(root, False)]

    while stack:
        node, processed = stack.pop()
        if processed:
            result.append(node.val)
            continue
        child_num = len(node.children)
        # 栈为后进先出结构，需要逆序压入待处理内容，保证弹出顺序符合遍历要求
        # 最先压入最右子树，最后处理
        if child_num > 0:
            stack.append((node.children[-1], False))
        # 压入当前节点，标记为已处理子节点，下次弹出直接取值
        stack.append((node, True))
        # 逆序压入前n-1棵子树，保证弹出时从左到右遍历
        for idx in range(child_num - 2, -1, -1):
            stack.append((node.children[idx], False))
    
    return result

测试示例 #

针对如下结构的多叉树：

1
    / | \
   2  3  4
     / \
    5   6

两个函数的返回结果均为[2, 5, 3, 6, 1, 4]，符合从左到右中序遍历的要求。

内容的提问来源于stack exchange，提问作者john smith