[알고리즘] [재 귀 편] [트 리] 8 절: leetcode 102. 이 진 트 리 의 층 차 를 옮 겨 다 니 기 (BFS 와 DFS)

이번 퀘 스 트: leetcode 에 있 는 나무의 전형 적 인 문제 에 대한 재 귀적 해법 을 소개 합 니 다.
[알고리즘] [재 귀 편] [나무] 제1 절: leetcode 100. 같은 나무
[알고리즘] [재 귀 편] [나무] 제2 절: leetcode 105. 이전 순서 와 중간 순서 가 서열 구조 이 진 트 리 를 옮 겨 다 녔 습 니 다.
[알고리즘] [귀속 편] [나무] 제3 절: leetcode 210. 교과 과정 표 II
[알고리즘] [재 귀 편] [나무] 4 절: leetcode 236. 이 진 트 리 의 최근 공공 조상
[알고리즘] [재 귀 편] [나무] 5 절: leetcode 572. 다른 나무의 서브 트 리
[알고리즘] [재 귀 편] [나무] 제6 절: leetcode 101. 대칭 이 진 트 리
[알고리즘] [재 귀 편] [트 리] 7 절: leetcode 98. 이 진 트 리 검증
[알고리즘] [재 귀 편] [나무] 8 절: leetcode 102. 이 진 트 리 의 층 차 를 옮 겨 다 닙 니 다.
문제 의 근원

102. 이 진 트 리 의 층 차 를 옮 겨 다 닌 다

102.         
       ，                  。 （    ，          ）。



  ：
   ：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
         ：

[
  [3],
  [9,20],
  [15,7]
]

키다리

교체 + 재 귀 다 중 그림 으로 102. 이 진 트 리 의 차원 을 보 여 줍 니 다

코드

"""
  ：
           ，                  。 （    ，          ）。
    
  1：
        （BFS）：            ，       ，          ，     
    
  2：
        （DFS）：    ，         index，          
    
"""


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def levelOrder(self, root: TreeNode):
        """    （DFS）：    ，         index，          """

        if not root:
            return []

        ans = list()

        def helper(index, node):
            if len(ans) <= index:
                ans.append([])

            #       
            ans[index].append(node.val)
            if node.left:
                helper(index + 1, node.left)
            if node.right:
                helper(index + 1, node.right)

        helper(0, root)
        return ans

    def levelOrder1(self, root: TreeNode):
        #     （BFS）：            ，       ，          ，     
        if not root:
            return []

        ans = list()
        queue = [root]
        while queue:
            #          ，                  
            size = len(queue)
            res = list()
            for i in range(size):
                #            (           )，    list 
                #       /      ，      
                node = queue.pop(0)
                res.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(res)  #    list         
        return ans