Binary Tree Level Order Traversal Problem


Description

LeetCode Problem 102.

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

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

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
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> levelOrder;
        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;
            
        }
        return levelOrder;
    }
};




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...