[leetcode] 102. Binary Tree Level Order Traversal

원문)

Given a binary tree, return the level traversal of its nodes's values.

번역)

이진트리를 주어졌을때 그 노드값을 level 순회를 반환하라.


예제)

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

문제접근)

top-down은 레벨을 기록해서 같은 level만 따로 분류
bottom-up도 같은 동작방식으로

코드)

1.  top-down

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

# 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) -> List[List[int]]: answer = [] self.top_down(root, 0, answer) return answer def top_down(self, root: TreeNode, level: int, answer: List[List[int]]): if root is None: return if len(answer) == level: answer.append([]) answer[level].append(root.val) self.top_down(root.left, level + 1, answer) self.top_down(root.right, level + 1, answer)

2. bottom-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

# 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) -> List[List[int]]: answer = [] stack = [(root, 0)] while stack: cur, level = stack.pop() if cur: if len(answer) == level: answer.append([]) answer[level].append(cur.val) stack.append((cur.right, level + 1)) stack.append((cur.left, level + 1)) return answer