Binary Tree Level Order Traversal II — LeetCode 107 Python Solution
MediumTreeBreadth-First SearchBinary Tree
- Problem
- #107
- Pattern
- Tree Traversal
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).
Example
- Input
- root = [3,9,20,null,null,15,7]
- Output
- [[15,7],[9,20],[3]]
Python solution
Python
# 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]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t)
return ans[::-1]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 107. Binary Tree Level Order Traversal II is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
LeetCode 102Binary Tree Level Order TraversalMediumLeetCode 103Binary Tree Zigzag Level Order TraversalMediumLeetCode 919Complete Binary Tree InserterMediumLeetCode 958Check Completeness of a Binary TreeMediumLeetCode 1609Even Odd TreeMediumLeetCode 2471Minimum Number of Operations to Sort a Binary Tree by LevelMedium
Frequently asked questions
- How hard is LeetCode 107. Binary Tree Level Order Traversal II?
- LeetCode 107. Binary Tree Level Order Traversal II is rated Medium on LeetCode.
- What is the time complexity of LeetCode 107. Binary Tree Level Order Traversal II?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 107. Binary Tree Level Order Traversal II?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 107. Binary Tree Level Order Traversal II cover?
- LeetCode 107. Binary Tree Level Order Traversal II is tagged Tree, Breadth-First Search and Binary Tree on LeetCode.