LC 102 & LC 107 & LC 199

Queue BFS
Binary Tree
Publish Date:   2022-05-21

Solution to LeetCode 102 Binary Tree Level Order Traversal, LeetCode 107 Binary Tree Level Order Traversal II, and LeetCode 199 Binary Tree Right Side View.

LeetCode 102

Binary Tree Level Order Traversal (Medium) [link]

Time complexity O(n).

# 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]]:
        que = deque([root])
        results = []
        if not root: return results
        
        while que:
            res = []
            size = len(que)
            
            for i in range(size):
                cur = que.popleft()
                res.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(res)

        return results

LeetCode 107

Binary Tree Level Order Traversal II (Medium) [link]

Time complexity O(n).

# 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: Optional[TreeNode]) -> List[List[int]]:
        results = []
        if not root: return results
        que = deque([root])
        while que:
            size = len(que)
            res = []
            for i in range(size):
                cur = que.popleft()
                res.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(res)
        results.reverse()
        return results

LeetCode 199

Binary Tree Right Side View (Medium) [link]

Level-order traversal the tree, while only record the last node of each level. Time complexity O(n).

# 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 rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        if not root:
            return res
        que = deque([root])
        while que:
            node = que[-1]
            res.append(node.val)
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)

        return res
Queue BFS
  TOC