leetcode-binary tree

107. Binary Tree Level Order Traversal II.py

# 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 levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        """
        BFS for binary tree vs BFS for graph 
            1. without the need of visited array
            2  the neighbor is left node and right node only.
        
        T:O(n)
        S:O(n)
        """
        if root is None:
            return []
        self.ans = []
        def bfs(root):
            q = collections.deque([(root, 0)]) # (node, level)
            while len(q) != 0:
                cur_node, level = q.popleft()
                if level == len(self.ans):
                    self.ans.append([])
                self.ans[level].append(cur_node.val)
                l, r = cur_node.left, cur_node.right # neighbor
                if l is not None:
                    q.append((l, level +1))
                if r is not None:
                    q.append((r, level +1))
        bfs(root)
        return self.ans[::-1]