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

Word Ladder Problem

LeetCode 127. Given two words, beginWord and endWord, and a...

Word Ladder II Problem

LeetCode 126. Given two words, beginWord and endWord, and a...

Surrounded Regions Problem

LeetCode 130. Given an m x n matrix board containing...

Binary Tree Zigzag Level Order Traversal Problem

LeetCode 103. Given the root of a binary tree, return...

Binary Tree Level Order Traversal Problem

LeetCode 102. Given the root of a binary tree, return...

Binary Tree Level Order Traversal II Problem

LeetCode 107. Given the root of a binary tree, return...