Python实现BST右视图时两种for循环写法结果差异原因咨询

可正常运行的正确实现 #

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []

        result = []
        
        q = []
        q.append(root)
        
        while len(q):
            # 关键差异行
            for _ in range(len(q)):
                node = q.pop(0)
                if node.left != None:
                    q.append(node.left)
                    
                if node.right != None:
                    q.append(node.right)
            result.append(node.val)
        
        return result

该实现针对测试用例root = [1,2,3,null,5,null,4]可输出正确结果[1,3,4]。

存在问题的错误实现 #

仅将循环行替换为直接遍历队列for _ in (q):，其余逻辑不变：

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if root == None:
            return []

        result = []
        
        q = []
        q.append(root)
        
        while len(q):
            # 改动后的差异行
            for _ in (q):
                node = q.pop(0)
                if node.left != None:
                    q.append(node.left)
                    
                if node.right != None:
                    q.append(node.right)
            result.append(node.val)
        
        return result

相同测试用例下该实现输出错误结果[2,5,4]。

差异核心原理 #

两种写法的本质区别是for循环的迭代边界是否在启动时固定：

• for _ in range(len(q))的逻辑：
  range()函数会在for循环启动的瞬间，读取当时队列的长度值，生成一个固定长度的整数迭代序列。后续循环过程中不管怎么对队列做pop出队、append入队操作，循环的执行次数都和刚进入循环时的队列长度完全一致，刚好把当前层的所有节点处理完，不会触碰循环中新加入的下一层节点，完全符合BFS层序遍历按层分割的要求。每次内层for循环结束时，最后一个被pop的节点就是当前层最右侧的节点，将其值加入结果集即可得到正确的右视图。
• for _ in q的逻辑：
  Python中直接遍历列表时，迭代器会动态跟踪列表的长度和元素位置：从索引0开始逐位取元素，每取完一个元素索引自增，直到索引超出列表当前实时长度才会停止遍历。
  你在内层循环中持续执行pop(0)移除队首元素，又持续将子节点追加到队尾，队列的长度、元素位置在整个循环过程中一直动态变化，迭代器会遍历到所有循环过程中新加入的元素，完全打破了「每次内层循环只处理一层节点」的边界。内层for循环结束时拿到的最后一个node根本不是当前层的最右节点，自然会输出错误结果。

初始阶段流程示例：初始队列q=[1]进入while循环，启动对q的遍历，第一次迭代取出节点1，将其左右孩子2、3加入队列，此时q变为[2,3]；迭代器不会因为初始q只有1个元素就停止，会继续取当前q的下一位元素，持续处理后续新加入的节点，完全跨层执行，最终第一层for循环结束时最后留存的node值为2，被错误加入结果集，后续逻辑也全部错位。

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