leetcode4-102. Binary Tree Level Order Traversal

1. problem

1. level order traversal of its nodes’ values. e.g.

   Input: root = [3,9,20,null,null,15,7]
   Output: [[3],[9,20],[15,7]]

2. like BFS

2. init

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

3. thought

• iterator

1. init stack root
2. open it and add val into [], result append it.
3. add it’s child into stack. left first.
4. iterate each item in stack.

• recursive

1. global list, clean in init
2. add [] in lsit when first time traverse to this depth.
3. add val in depth list

4. trouble

• iterator
  1. keep same level node in stack
  2. one func
• recursive
  1. fill node’s val in certain position
  2. two func, one global list

5.final solution

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 1. init stack root
        # 2. open it and add val into [], result append it.
        # 3. add it's child into stack. left first.
        # 4. iterate each item in stack.
        if root is None: return []
        result, stack = [], [[root]] # init stack has root
        while stack:
            nodes = stack.pop() # keep pop all item in the stack
            currentLevel = [] # help currnt level into bracket
            childs = [] # load next level child
            for node in nodes:
                currentLevel.append(node.val)
                if node.left: childs.append(node.left)
                if node.right: childs.append(node.right)
            result.append(currentLevel)
            if childs: stack.append(childs)
        return result

recursive way.

# https://leetcode.com/problems/binary-tree-level-order-traversal/solutions/33468
class Solution:
    # 1. init global list with empty []
    # 2. add empty [] in lsit when first time traverse to this depth.
    # 3. add val in list[depth]
    _list = []
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        self._list = []
        self.preOrder(root, 0)
        return self._list
    def preOrder(self, root: Optional[TreeNode], depth: int) -> List[List[int]]: 
        if not root: return
        if len(self._list)==depth: self._list.insert(depth,[]) 
        self._list[depth].append(root.val)
        if root.left: self.preOrder(root.left, depth+1)
        if root.right: self.preOrder(root.right, depth+1)

# case [3,9,20,null,null,15,7]
# 1. [[]]
# 2. [[3]]
# 3. [[3], []]
# 4. [[3], [9], []]
# 5. [[3], [9,20], []]
# 6. ...