python - 打印二叉树的顶 View

Question

我正在尝试打印二叉树的顶 View 。我在python中的代码如下:

class Node(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def top_view(root, m, hd):
    if root is None:
        return

    if hd not in m:
        m[hd] = root.data
        print hd

    top_view(root.left, m, hd-1)
    top_view(root.right,m, hd+1)

def print_top_view(root):
    m={}
    hd=0
    top_view(root, m, hd)
    for key,value in m.iteritems():
        print value,

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

然而，这给出了以下输出:1 2 5 6

而输出应该是:1 2 3 6

谁能解释一下我哪里做错了？

Answer 1

您正在按深度优先顺序遍历树。 IE。您正在调用 top_view(root.left, m, -1)，它将递归搜索树的整个左侧。因此，当您调用 top_view(root.right, m, 1) 时，您已经将 m[1] 设置为节点 5，并且最终不会将节点 3 放入。

我认为有两种方法可以解决这个问题:

1) 使用队列而不是递归 - 即首先处理级别 0 的所有节点，然后处理级别 1 的所有节点，等等。

2) 在递归中将深度作为参数传递，并将(节点，深度)对存储在 m 字典中。然后，即使 hd 在 m 中，如果它的深度小于当前在 m 中的节点，则用一个新节点覆盖它。