검지 Offer 32 - II.위에서 아래로 두 갈래 트리 인쇄 II(양끝 대기열)

2167 단어
  • 제목 묘사
  •  , , 。
    
     
    
     :
     : [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
     :
    
    [
      [3],
      [9,20],
      [15,7]
    ]
     
    
     :
    
      <= 1000
  • 해법: 양단 대기열

  • 위에서 아래로 두 갈래 트리 I를 인쇄하는 것을 참고하십시오. 주로 deque로 모든 층의 노드를 저장합니다.
    class Solution:
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if not root:
                return []
            queue = collections.deque()
            res = []
            queue.append(root)
            while queue:
                tmp = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    tmp.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                res.append(tmp)
            return res

    시간 복잡도 O(N) O(N): NN은 두 갈래 트리의 노드 수량입니다. 즉, BFS는 NN회를 순환해야 합니다.공간 복잡도 O(N) O(N): 최악의 경우, 트리가 균형 두 갈래 트리일 때, 최대 N/2N/2개의 트리 노드가 동시에queue에서 O(N) O(N) 크기의 추가 공간을 사용합니다.

    좋은 웹페이지 즐겨찾기