python - 打印二叉树的顶 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

谁能解释我在哪里做错了？

最佳答案

您正在以深度优先的顺序遍历树。即您正在调用top_view（root.left，m，-1），它将递归搜索树的整个左侧。因此，当您调用top_view（root.right，m，1）时，已经在节点5上设置了m [1]，并且最终没有将节点3放入。

我认为有两种方法可以解决此问题：

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

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

关于python - 打印二叉树的顶 View ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38215320/