↓Skip to main content

LeetCode 107: Binary Tree Level Order Traversal II

2022-11-18·1 min· ·

LeetCode Medium Tree Breadth-First-Search Binary-Tree

Author

Wei Yi Chung

Working at the contributing of open source, distributed systems, and data engineering.

Table of Contents

Table of Contents

Meta Data
#

Difficulty: medium First Attempt: 2022-11-18

Submissions: Accepted ×2

Approach
#

Collect level by level as in LC 102 (Tree Template 2), then reverse the whole result so it starts from the bottom level.

My Solution
#

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res, level = [], [root] if root else []
        while level:
            res.append([n.val for n in level])
            level = [c for n in level for c in (n.left, n.right) if c]
        return res[::-1]

Complexity
#

Time O(n), space O(n).

Mistakes to Avoid
#

Reverse the order of levels; each level stays left to right.

Interview Explanation
#

I collect levels with a normal BFS and reverse their order at the end. Time O(n).

Related

LeetCode 103: Binary Tree Zigzag Level Order Traversal

2022-11-18·1 min

LeetCode Medium Tree Breadth-First-Search Binary-Tree

LeetCode 103 note: a normal level-order traversal with every odd level reversed gives the zigzag

LeetCode 102: Binary Tree Level Order Traversal

2022-10-29·1 min

LeetCode Medium Tree Breadth-First-Search Binary-Tree

LeetCode 102 note: BFS one whole level at a time, building the next level from the current one; an empty tree returns an empty list

LeetCode 1448: Count Good Nodes in Binary Tree

2022-10-29·1 min

LeetCode Medium Tree Depth-First-Search Breadth-First-Search Binary-Tree

LeetCode 1448 note: pass the path maximum down during DFS; a node is good when its value is at least that maximum

LeetCode 199: Binary Tree Right Side View

2022-10-29·1 min

LeetCode Medium Tree Depth-First-Search Breadth-First-Search Binary-Tree

LeetCode 199 note: in a level-order traversal, each level’s rightmost node is what you see from the right

LeetCode 1379: Find a Corresponding Node of a Binary Tree in a Clone of That Tree

2022-11-17·1 min

LeetCode Easy Tree Depth-First-Search Breadth-First-Search Binary-Tree

LeetCode 1379 note: walk both trees in lockstep; when the original reaches target, the clone’s node at the same position is the answer, comparing node identity

LeetCode 113: Path Sum II

2022-11-18·2 mins

LeetCode Medium Backtracking Tree Depth-First-Search Binary-Tree

LeetCode 113 note: backtrack with the current path and store a copy at a leaf whose total matches; values can be negative, so no early pruning