python 中二叉树的顶视图

Question

我正在尝试解决 geeksforgeeks.com

Given below is a binary tree. The task is to print the top view of binary tree. Top view of a binary tree is the set of nodes visible when the tree is viewed from the top. For the given below tree
      1
   /    \
  2      3
 / \    / \
4   5  6   7
Top view will be: 4 2 1 3 7

Note: Return nodes from leftmost node to rightmost node.

谁能告诉我我的代码哪里错了？它适用于我尝试过的大多数情况，但对于太长而无法干燥的情况则失败了运行.

class Solution:
  
    #Function to return a list of nodes visible from the top view 
    #from left to right in Binary Tree.

    def topView(self,root):
        left_ans = []
        def left_view(root,level) :
            if not root : return 
            if level > len(left_ans) : left_ans.append(root.data)
            left_view(root.left,level+1)
            left_view(root.right,level-1)
        
        right_ans = []
        def right_view(root,level) :
            if not root: return
            if level > len(right_ans) : right_ans.append(root.data)
            right_view(root.right,level+1)
            right_view(root.left,level-1)
        
        left_view(root,level = 1)
        right_view(root,level =1)
        
        return left_ans[::-1]+right_ans[1:]

失败的树：

               __________________23______________________
              /                                          \
          __17__                        _________________65__________________ 
         /      \                      /                                     \
      __9__      19            ______38_______                             __69__
     /     \    /  \          /               \                           /      \
    7      10  18  21       37       __________43__________              67      74
   / \       \    /  \     /        /                      \            /  \    /
  1   8      14  20  22  33       39                _______53_______   66  68  70
   \        /  \        /        /  \              /                \            \
    4      13  16   __29_      35   40           51                _62_          71 
   / \    /   /    /     \    /  \    \         /  \              /    \           \
  3   5  11  15  27      32  34  36   41      45   52          __58__  63          72 
 /     \   \    /  \    /               \    /  \             /      \   \           \
2       6  12  24  28  30               42  44   47          57      61  64          73
                 \       \                      /  \        /       /
                 26      31                    46  49      55      60 
                /                                 /  \    /  \    /
               25                                48  50  54  56  59

预期输出：

2 1 7 9 17 23 65 69 74 63 64

我的代码输出（错误）：

2 1 7 9 17 23 65 69 74 72 73

Answer 1

您的算法假定首先访问最高节点，但情况并非总是如此。这是一个最小的例子：

注意从根开始spring的两个分支，向下交叉两层（11的左边child是10，1的右边child是2).由于您首先访问左子树，因此您将注册 3 从顶部可见。当您稍后遍历另一条路径时，它不会更新。

一个解决方案是保持找到节点的深度。如果稍后，在相同的垂直偏移量 (level) 处找到另一个候选节点，您可以比较这两个节点的深度并确定哪个节点在另一个节点之上。

第二个问题是挑战中提到解决方案应该 "Return 个从最左边的节点到最右边的节点。"。这个说法有点模棱两可，但似乎是指当两个节点高度相同，垂直偏移量相同时，应该优先遍历left-first找到的节点。但在 right_view 中你使用了相反的顺序：只需更改递归调用的顺序。

这是使用 depth 和固定递归 call-order 概念更新的函数：

def topView(self,root):
    left_ans = []
    left_depth = []
    def left_view(root,level,depth) :
        if not root:
            return 
        if level >= 0:
            if level >= len(left_ans): 
                left_ans.append(root.data)
                left_depth.append(depth)
            elif depth < left_depth[level]:
                left_ans[level] = root.data
                left_depth[level] = depth
        left_view(root.left,level+1,depth+1)
        left_view(root.right,level-1,depth+1)
    
    right_ans = []
    right_depth = []
    def right_view(root,level,depth):
        if not root:
            return
        if level >= 0:
            if level >= len(right_ans): 
                right_ans.append(root.data)
                right_depth.append(depth)
            elif depth < right_depth[level]:
                right_ans[level] = root.data
                right_depth[level] = depth
        right_view(root.left,level-1,depth+1)
        right_view(root.right,level+1,depth+1)
    
    left_view(root,0,0)
    right_view(root,0,0)

    return left_ans[::-1]+right_ans[1:]

python 中二叉树的顶视图

Top view of a Binary tree in python

tree

binary-tree

python-3.x