Tress DSA（运行代码时出现问题）

Question

我正在尝试找出二叉树的顶视图。该代码在自定义测试用例上运行正确，但每当我尝试提交它时，它都会在同一输入上显示不同的输出。平台是gfg。

我已经尝试了以下代码，它在大多数测试用例中都能正确运行。

    def topView(self,root):
        
        # code here
        
        map = defaultdict(list)
        queue = [[root , 0]]
    
        while queue:
    
            top , dim = queue.pop(0)
            if not map[dim] : 
                map[dim] = top.data
            
            if top.left:
                queue.append([top.left,  dim - 1])
            if top.right:
                queue.append([top.right,dim + 1])
    
        
        map = dict(sorted(map.items()))
        ans = []
        for key in map:
            ans.append(map[key])
        return ans

Answer 1

您的代码使用列表来实现队列，这会导致从前面弹出的效率低下（

queue.pop(0)

）。这使得您的代码

O(n^2)

。

相反，请考虑使用

collections.deque

来表示

O(1)

弹出：

from collections import deque, defaultdict

class Solution:
    
    def topView(self, root):
        dim_map = defaultdict(list)
        queue = deque([(root, 0)])
        while queue:
            top, dim = queue.popleft()
            if not dim_map[dim]:
                dim_map[dim] = top.data
            if top.left:
                queue.append((top.left, dim - 1))
            if top.right:
                queue.append((top.right, dim + 1))
        ans = [value for key, value in sorted(dim_map.items())]
        return ans

这应该通过所有测试用例。