Leetcode 107. Binary Tree Level Order Traversal II

Problem Explanation

The problem asks for a bottom-up level order traversal of a binary tree. Level order traversal is a breadth-first traversal that visits all the nodes at the current level before moving on to the next level. However, instead of the traditional top-down traversal (from root to leaves), we want a bottom-up traversal (from leaves to root).

For example, given the binary tree:

1     3
2   /   \
3  9    20
4      /     \
5     15      7

The bottom-up level order traversal is: [[15,7], [9,20], [3]]

Solution Approach

The solution will use a queue, a common approach for level order traversals in trees. The algorithm involves the following steps:

1. Initialize a queue and add the root node into it.

2. Iterate while the queue is not empty. At each iteration:

   • Initialize a temporary list to store the values of the current level.
   • Iterate over each node at the current level (i.e., the size of the queue before we dequeue any nodes), get the value of the node and add it to the temporary list. Also, add the left and right children of the node, if exist, into the queue.
   • Add the temporary list into the result list.

3. At the end of the algorithm, reverse the result list to get bottom-up level order traversal.

Solution in Python

1
2python
3class Solution:
4  def levelOrderBottom(self, root):
5    if root is None:
6      return []
7
8    res, queue = [], [root]
9    while queue:
10      res.append([node.val for node in queue])
11      queue = [child for node in queue for child in (node.left, node.right) if child]
12    return res[::-1]

Here the Python solution follows the approach as explained above. We use a list comprehension to implement the queue and make use of Python's slicing features ([::-1]) to reverse the list easily.

Solution in Java

1
2java
3class Solution {
4  public List<List<Integer>> levelOrderBottom(TreeNode root) {
5    List<List<Integer>> res = new LinkedList<>();
6    if (root == null)
7      return res;
8        
9    Queue<TreeNode> queue = new LinkedList<>();
10    queue.offer(root);
11        
12    while (!queue.isEmpty()) {
13      int size = queue.size();
14      List<Integer> level = new ArrayList<>();
15      for (int i = 0; i < size; i++) {
16        TreeNode curr = queue.poll();
17        if (curr.left != null)
18          queue.offer(curr.left);
19        if (curr.right != null)
20          queue.offer(curr.right);
21        level.add(curr.val);
22      }
23      res.add(0, level);
24    }
25    return res;
26  }
27}

In Java, we use Queue interface for the queue, and a LinkedList to implement the bottom-up level order traversal. We add each new level list at the beginning of the result list (res.add(0, level)), which gives us a bottom-up traversal without having to reverse the result.

Solution in JavaScript

1
2javascript
3class Solution {
4  levelOrderBottom(root) {
5    if (!root) {
6      return [];
7    }
8
9    let res = [], queue = [root];
10    while (queue.length) {
11      let level = [], len = queue.length;
12      for (let i = 0; i < len; i++) {
13        let node = queue.shift();
14        level.push(node.val);
15        if (node.left) {
16          queue.push(node.left);
17        }
18        if (node.right) {
19          queue.push(node.right);
20        }
21      }
22      res.unshift(level);
23    }
24
25    return res;
26  }
27}

The JavaScript solution Array's shift operation removes the first element (Dequeues), push operation adds elements to the end (Enqueues), and unshift operation adds an element to the beginning of the list.

Solution in C++

1
2c++
3class Solution {
4 public:
5  vector<vector<int>> levelOrderBottom(TreeNode* root) {
6    if (!root)
7      return {};
8
9    vector<vector<int>> ans;
10    queue<TreeNode*> q{{root}};
11
12    while (!q.empty()) {
13      vector<int> currLevel;
14      for (int sz = q.size(); sz > 0; --sz) {
15        TreeNode* node = q.front();
16        q.pop();
17        currLevel.push_back(node->val);
18        if (node->left)
19          q.push(node->left);
20        if (node->right)
21          q.push(node->right);
22      }
23      ans.push_back(currLevel);
24    }
25
26    reverse(begin(ans), end(ans));
27    return ans;
28  }
29};

The C++ solution uses the STL's queue and vector to maintain the queue and result list. It uses the reverse function from the STL's algorithm to reverse the result.

Solution in C#

1
2csharp
3public class Solution {
4    public IList<IList<int>> LevelOrderBottom(TreeNode root) {
5        LinkedList<IList<int>> result = new LinkedList<IList<int>>();
6        if(root == null) {
7            return result.ToArray();
8        }
9        
10        Queue<TreeNode> nodes = new Queue<TreeNode>();
11        nodes.Enqueue(root);
12        while(nodes.Count > 0) {
13            int size = nodes.Count;
14            List<int> level = new List<int>();
15            for(int i = 0; i < size; i++) {
16                TreeNode curr = nodes.Dequeue();
17                level.Add(curr.val);
18                if(curr.left != null) {
19                    nodes.Enqueue(curr.left);
20                }
21                if(curr.right != null) {
22                    nodes.Enqueue(curr.right);
23                }
24            }
25            result.AddFirst(level);
26        }
27        return result.ToArray();
28    }
29}

The C# solution operates similarly to the Java solution above. This solution makes use of C#'s Queue and LinkedList data structures. It dequeues each node and enqueues its children, continually building and adding the level result to the beginning of the linked list to get a bottom-up result.This problem demonstrates a common application of the queue data structure in tree traversal problems. Generally, a breadth-first traversal in tree-based data structures involves the use of a queue. This is because, unlike depth-first strategies such as pre-order, in-order, and post-order traversals, which use recursion (or alternatively, a stack) to visit nodes in a top-down fashion starting from the leftmost leaf node, breadth-first strategies such as level order visit nodes 'horizontally' in a top-down fashion starting from the root.

A variation of the level order traversal as demonstrated in this problem is the bottom-up level order traversal, which visits nodes in a bottom-up fashion, from the leftmost leaf node to the root. This can be visualized as a 'zigzag' pattern. Applying this strategy using a queue involves:

1. Enqueueing the root node, which is considered to be at level 1.
2. Initializing a loop to continue until the queue is empty.
3. Initializing a container (such as a list or an array) to temporarily hold the nodes in the current level.
4. Iterating over the number of elements in the queue, dequeueing each one, adding its value to the temporary container, and enqueueing its child nodes (if they exist).
5. If the direction for the current level is from right to left, reversing the temporary container and adding it to the result.
6. After finishing the level, reversing the direction for the next level.
7. Repeating steps 3-6 until the queue is empty.

In conclusion, this problem helps to understand and differentiate between various tree traversal strategies and how they may be implemented using different data structures such as stacks and queues.

Aside from Python, Java, JavaScript, C++, and C#, this type of problem could also be solved in other languages like Ruby, Go, Rust, Swift, Kotlin, and so on, using similar strategies and the respective data structures and built-in functions available in the standard libraries of these languages.