leetcode medium : binary Tree Level Order Traversal

Binary Tree Level Order Traversal - LeetCode

Binary Tree Level Order Traversal - LeetCode

 

한 레벨의 노드들을 담는 리스트를 만들어서 풀었다.

루트 노드부터 각 레벨의 리스트를 만들어 순회하면서 result 리스트에 답을 추가하고

다음 리스트를 만들면 된다. 더이상 만들 수 있는 다음레벨 리스트가 없을때까지

 

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        level = []
        
        if not root:
            return []
        
        level.append(root)
        
        result = []
        while level:
            tmp = []
            
            nlevel = []
            for node in level:
                tmp.append(node.val)
                
                if node.left:
                    nlevel.append(node.left)
                if node.right:
                    nlevel.append(node.right)
            
            result.append(tmp[:])
            level = nlevel
            
        return result
                    

 

시간복잡도는 노드개수가 N일때 O(N)이고 공간복잡도는 O(2 ^ logN)일듯?

 

다른 방법으로 풀 수도 있다.

class Solution:
    def helper(self, result, node, level):
        if not node:
            return
        
        if len(result) <= level:
            result.append([])
            
        result[level].append(node.val)
        self.helper(result, node.left, level + 1)
        self.helper(result, node.right, level + 1)
        
    
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        result = []
        self.helper(result, root, 0)
        return result

근데 이건 성능이 영 안좋다 ㅋㅋㅋㅋ function call을 많이해서 그런듯!! 메모리도 많이 쓸수밖에없고

 

첨 작성했던 솔루션이 아무리 봐도 최적이다. 살짝의 변경만을 가해서 submission 결과를 향상시켜보았다

class Solution:

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

        if not root:
            return []
        
        level = [root]
        
        result = []
        while level:
            result.append(list(map(lambda x : x.val, level)))
            
            nlevel = []
            for node in level:
                if node.left:
                    nlevel.append(node.left)
                if node.right:
                    nlevel.append(node.right)
            
            level = nlevel
            
        return result