Leetcode 102. Binary Tree Level Order Traversal (BFS)

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode

 

---

 

Binary Tree는 간단하면서도 아직 완벽히 이해가 가지 않는 부분이기 때문에 여러 사람들의 코드를 보면서,

어떤 구조로 실제 프로그래밍 될 수 있는지 공부해보려 한다

 

 

---

√ Level Order기반 Binary Tree 풀이

Code Source: https://leetcode.com/problems/binary-tree-level-order-traversal/discuss/33464/5-6-lines-fast-python-solution-(48-ms)

 

List Comprehension을 활용한 풀이 )

def levelOrder(self,root):
	ans, level = [], [root]
    
    while root and level:
    	ans.append([node.val for node in leve])
        LRpair = [(node.left, node.right) for node in level]
        level = [l for LR in LRpair for l in LR if l]
    return ans

 

def levelOrder(self,root):
	ans, level = [], [root]
    
    while root and level:
    	ans.append([node.val for node in level])
        level = [kid for n in level for kid in (n.left,n.right) if kid]
    return ans

 

위 2개의 풀이는 사실 표현만 달리한 풀이인데요

ans는 답을 담는 그릇, level은 현재 레벨에 있는 node의 값들을 담는 그릇인데요

 

ans.append를 통해서 node.val을 먼저 담고, level 에서 자식노드 left,right을 담도록 해서 ans에 append 하고

level을 다음 단계의 자식노드로 업데이트 해서 ans에 담도록 했습니다.

 

 

자세한 단계별 풀이 )

def levelOrder(self,root):
	if not root: 
    	return []
        
    ans, level = [], [root]
    
    while level:
    	ans.append([node.val for node in level])
        
        temp = []
        for node in level:
        	temp.extend([node.left,node.right])
        level = [leaf for leaf in temp if leaf]
    return ans

 

 

Queue를 이용한 풀이 )

 

from collections import deque
class Solution(object):
    def levelOrder(self, root):
     
        q, result = deque([root]), []

        while len(q):
            level = []
            for _ in range(len(q)):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            result.append(level)
        return result

 

이 방법이 저는 제일 직관적으로 와닿았는데요

deque를 이용해서 첫번째 노드를 뽑고 level에 배정한 뒤에, 

비어있지 않은 자식노드 left,right을 다시 q에 넣고 node가 그 값을 뽑아서 level에 넣고

이 과정을 끝낸 level을 result에 담아 내는 방법입니다

 

binary tree는 아직 알듯 말듯 해서 계속 연습 해야겠습니다~~