[알고리즘] [재 귀 편] [트 리] 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
    

    좋은 웹페이지 즐겨찾기