[LeetCode][Python3] 102. Binary Tree Level Order Traversal

Problem :

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

My Solution :

# 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):

"""

:type root: TreeNode

:rtype: List[List[int]]

"""

ret, queue = [], [root]

while root and queue:

node_val, node_queue = [], []

for node in queue:

node_val.append(node.val)

if node.left:

node_queue.append(node.left)

if node.right:

node_queue.append(node.right)

ret.append(node_val)

queue = node_queue

return ret

Comment :

위 풀이는 다른 풀이를 참고한 것이고, 아래 풀이는 내가 처음 문제를 접했을 때 시도한 풀이이다.

My Solution2 :

# Definition for a binary tree node.

# class TreeNode:

# def __init__(self, x):

# self.val = x

# self.left = None

# self.right = None

from collections import deque

class Solution:

def levelOrder(self, root):

"""

:type root: TreeNode

:rtype: List[List[int]]

"""

dic = {}

queue = deque([(root, 0)])

while root and queue:

node, level = queue.popleft()

dic.setdefault(level, []).append(node.val)

if node.left:

queue.append((node.left, level+1))

if node.right:

queue.append((node.right, level+1))

ret = [dic[level] for level in sorted(dic)]

return ret