二叉树层序遍历Python嵌套循环无法终止问题求助

问题背景 #

正在解决LeetCode的二叉树层序遍历问题，采用列表模拟队列，通过双层循环实现——内层循环负责遍历处理树的每一层。

代码逻辑概述 #

• 用列表q作为队列存储节点，初始时加入root节点和标记-1（标识第一层结束）；
• 外层循环持续到队列为空；
• 内层循环处理当前层节点：出队节点，若为标记-1则将当前层结果加入res，添加新标记后跳出内层循环；若为有效节点则记录值，并将左右子节点入队。

遇到的问题 #

程序触发break语句后仍无法终止，日志中已打印“break outer loop”但程序继续执行，还出现了输入树中不存在的val为1的节点。尝试过设置终止标志、在内层直接返回结果，均无效。

使用的代码 #

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        q = []
        q.append(root)
        q.append(-1)
        res = []
        while len(q) != 0:
            cur = []
            while len(q) != 0:
                node = q.pop(0)
                print(q, node)
                if node == -1:
                    if len(q) == 0:
                        print("End")
                        break
                    res.append(cur)
                    q.append(-1)
                    break
                cur.append(node.val)
                if node.left != None:
                    q.append(node.left)
                if node.right != None:
                    q.append(node.right)
            if len(q) == 0:
                print("break outer loop")
                break
        return res

输入树结构 #

运行日志 #

[-1] TreeNode{val: 3, left: TreeNode{val: 9, left: None, right: None}, right: TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}}
[TreeNode{val: 9, left: None, right: None}, TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}] -1
[TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}, -1] TreeNode{val: 9, left: None, right: None}
[-1] TreeNode{val: 20, left: TreeNode{val: 15, left: None, right: None}, right: TreeNode{val: 7, left: None, right: None}}
[TreeNode{val: 15, left: None, right: None}, TreeNode{val: 7, left: None, right: None}] -1
[TreeNode{val: 7, left: None, right: None}, -1] TreeNode{val: 15, left: None, right: None}
[-1] TreeNode{val: 7, left: None, right: None}
[] -1
End
break outer loop <- The program was supposed to end here.
[-1] TreeNode{val: 1, left: None, right: None} <- No clue from where it is getting a node with value 1
[] -1
End
break outer loop
[-1] None

问题分析与修复方案 #

核心问题 #

1. 标记-1的逻辑漏洞：当处理最后一层节点后，遇到-1时因队列为空，仅跳出内层循环但未将当前层的cur列表加入结果集res，导致结果缺失；
2. 循环终止逻辑混乱：原依赖-1标记的双层循环容易出现边界情况处理不当，比如队列中残留标记或节点未被完全处理；
3. 日志中的异常节点：出现val=1的节点和None，大概率是测试框架多次调用该函数（测试不同用例），并非单次执行无法终止，但原代码的逻辑缺陷放大了这个问题。

修复后的代码（标准层序遍历实现） #

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    q = [root]
    res = []
    while q:
        # 记录当前层的节点数量，确保内层循环只处理当前层
        level_size = len(q)
        cur_level = []
        for _ in range(level_size):
            node = q.pop(0)
            cur_level.append(node.val)
            # 子节点入队
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(cur_level)
    return res

修复说明 #

• 移除了易出错的-1标记方案，改用记录当前层节点数量的方式，这是层序遍历的标准实现，逻辑清晰且无边界漏洞；
• 增加了空树判断，直接返回空列表，避免空指针异常；
• 外层循环每次处理完整一层，内层循环严格按照当前层节点数量执行，确保所有节点被正确处理，不会出现循环无法终止的问题。

内容的提问来源于stack exchange，提问作者Dhanesh Walte