[LeetCode] 107. Binary Tree Level Order Traversal II

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

Use BFS traverse the given tree and record the passed node values.

# 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]]:
        if not root:
            return []
        
        # bfs
        queue = deque([root])
        result = []
        
        while queue:
            level = deque()
            tmp = []
            
            while queue:
                node = queue.popleft()
                
                tmp.append(node.val)
                
                if node.left:
                    level.append(node.left)
                    
                if node.right:
                    level.append(node.right)
            
            queue = level
            result.insert(0, tmp)
        
        return result

DFS solution

# 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]]:
        if not root: return []
        
        # dfs
        result = []
        stack = [(root, 0)]
        
        while stack:
            node, level = stack.pop()
            
            if level == len(result):
                result.append([node.val])
            else:
                result[level].append(node.val)
            
            if node.right:
                stack.append((node.right, level+1))
            
            if node.left:
                stack.append((node.left, level+1))
        
        return result[::-1]

Edited on 06/06/2021. Add the DFS solution.