二叉树左视图Python实现错误排查求助

给定二叉树结构：

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

预期左视图为 1, 2, 4，但代码输出结果为 1, 2, 4, 8，错误包含了右子树的节点8。以下是原实现代码：

# left view method
class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.data = val

class Leftview:
    def view(self, root):
        out = []
        maxlevel = [-1]
        self._helperrecur(root, 0, maxlevel, out)
        for i in range(len(out)):
            print(out[i], end=' ')
        

    def _helperrecur(self, root, level, maxlevel, out):

        #base condition
        if root is None:
            return
        
        #main condition
        if level > maxlevel[0]:
            out.append(root.data)
            maxlevel[0] = level

        #recursive through tree
        self._helperrecur(root.left, level+1, maxlevel, out)
        self._helperrecur(root.right, level+1, maxlevel, out)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)

lf = Leftview()
lf.view(root)

错误原因分析 #

原代码的核心逻辑是只要当前节点的层级大于已记录的最大层级，就将其加入左视图，但这个逻辑存在漏洞：
当左子树的某一层没有任何节点时，右子树中对应层级的节点会被误判为该层的第一个节点。比如节点8处于第3层，此时左子树的第3层（节点4的左右子节点）为空，遍历到节点8时，它的层级3大于当前maxlevel的2，因此被错误加入左视图，但实际上该层没有左节点，左视图不应包含这个节点。

左视图的定义是每一层的最左侧节点，原逻辑没有保证只有左子树的节点优先被记录，而是只要层级更深就记录，导致右子树的深层节点“钻空子”被加入。

修正方案 #

修改递归中的判断条件，利用out数组的长度来判断是否为当前层级的第一个节点（因为优先遍历左子树，所以第一个到达该层级的节点必然是最左侧的），同时可以移除冗余的maxlevel变量。

修正后的完整代码：

# left view method
class Node:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.data = val

class Leftview:
    def view(self, root):
        out = []
        self._helperrecur(root, 0, out)
        for i in range(len(out)):
            print(out[i], end=' ')
        

    def _helperrecur(self, root, level, out):
        if root is None:
            return
        
        # 只有当当前层级等于已收集的节点数时，才加入（说明是该层第一个节点）
        if level == len(out):
            out.append(root.data)

        # 优先遍历左子树，保证左节点先被处理
        self._helperrecur(root.left, level+1, out)
        self._helperrecur(root.right, level+1, out)


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
root.right.left.right = Node(8)

lf = Leftview()
lf.view(root)

修正逻辑说明 #

• out数组的长度等于已经收集的左视图节点数，对应已处理完成的层级数（从0开始计数）。例如out有3个元素时，说明已经处理了0、1、2层，只有当节点层级为3且是第一个到达该层级的节点时，才会被加入。
• 始终优先遍历左子树，确保同一层级中左节点先被访问，这样第一个触发level == len(out)的节点必然是该层最左侧的节点，不会让右子树的节点误加入。

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