Binary Tree Level Order Traversal II Problem


Description

LeetCode Problem 107.

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 1:

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

Example 2:

1
2
Input: root = [1]
Output: [[1]]

Example 3:

1
2
Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> levelOrder, reverseLevelOrder;
        queue<TreeNode*> bfsQ;
        queue<int> levelQ;
        if (root == NULL)
            return levelOrder;
        bfsQ.push(root);
        levelQ.push(1);
        

        TreeNode* curr;
        vector<int> currLevel;
        int level;
        int lastLevel = 1;
        while (!bfsQ.empty()) {
            curr = bfsQ.front();
            bfsQ.pop();
            level = levelQ.front();
            levelQ.pop();
            if (level > lastLevel) {
                levelOrder.push_back(currLevel);
                currLevel.clear();
            }
            if (curr != NULL) {
                currLevel.push_back(curr->val);
                bfsQ.push(curr->left);
                bfsQ.push(curr->right);
                levelQ.push(level+1);
                levelQ.push(level+1);
            }    
            lastLevel = level;
            
        }
        for (vector<vector<int>>::reverse_iterator rvit = levelOrder.rbegin(); 
            rvit != levelOrder.rend(); rvit ++) {
            reverseLevelOrder.push_back(*rvit);
        }
        return reverseLevelOrder;
    }
};




Related Posts

Snakes And Ladders Problem

LeetCode 909. You are given an n x n integer...

Rotting Oranges Problem

LeetCode 994. You are given an m x n grid...

Numbers With Same Consecutive Differences Problem

LeetCode 967. Return all non-negative integers of length n such...

K-Similar Strings Problem

LeetCode 854. Strings s1 and s2 are k-similar (for some...