Algorithm
Problem Nmae: 102. Binary Tree Level Order Traversal
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:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
struct TreeNode **q;
int n;
int sz;
} q_t;
void add2q(q_t *q, struct TreeNode *node) {
if (q->n == q->sz) {
q->sz *= 2;
q->q = realloc(q->q, q->sz * sizeof(struct TreeNode *));
//assert(q->q);
}
q->q[q->n ++] = node;
}
int depth(struct TreeNode *node) {
int l, r;
if (!node) return 0;
l = depth(node->left) + 1;
r = depth(node->right) + 1;
if (l > r) return l;
return r;
}
void bfs(int **p, q_t *q1, q_t *q2, int *c, int d) {
int *buff, buffsz, i;
struct TreeNode *node;
if (!q1->n) return;
buffsz = 10;
buff = malloc(buffsz * sizeof(int));
for (i = 0; i < q1->n; i ++) {
node = q1->q[i];
//printf("%d, ", node->val);
if (c[d] >= buffsz) {
buffsz *= 2;
buff = realloc(buff, buffsz * sizeof(int));
//assert(buff);
}
buff[c[d]] = node->val;
c[d] ++;
if (node->left) add2q(q2, node->left);
if (node->right) add2q(q2, node->right);
}
//printf("done!\n");
p[d] = buff;
q1->n = 0;
bfs(p, q2, q1, c, d + 1);
}
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize) {
int d;
int **p, *c;
q_t q1 = { 0 }, q2 = { 0 };
*returnSize = 0;
if (!root) return NULL;
d = depth(root);
p = malloc(d * sizeof(int *));
c = calloc(d, sizeof(int));
//assert(p && c);
q1.sz = q2.sz = 10;
q1.q = malloc(q1.sz * sizeof(struct TreeNode *));
q2.q = malloc(q2.sz * sizeof(struct TreeNode *));
//assert(q1.q && q2.q);
add2q(&q1, root);
bfs(p, &q1, &q2, c, 0);
*returnSize = d;
*columnSizes = c;
free(q1.q);
free(q2.q);
return p;
}
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector < vector<int>>res;
if(!root) return res;
deque < TreeNode*>cur;
dequenext;
cur.push_back(root);
int level = 0;
res.push_back(vector<int>());
while(!cur.empty()){
TreeNode* node = cur.front();
cur.pop_front();
if(node->left) next.push_back(node->left);
if(node->right) next.push_back(node->right);
res[level].push_back(node->val);
if(cur.empty() && !next.empty()){
res.push_back(vector<int>());
level++;
swap(cur, next);
}
}
return res;
}
};
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
}
Queue queue = new LinkedList<>();
List < List();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List < Integer> currLevel = new ArrayList<>();
while (size-- > 0) {
TreeNode removed = queue.remove();
currLevel.add(removed.val);
if (removed.left != null) {
queue.add(removed.left);
}
if (removed.right != null) {
queue.add(removed.right);
}
}
result.add(currLevel);
}
return result;
}
}
Input
root = [1]
Output
[[1]]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const levelOrder = function(root) {
const res = [];
if (root == null) return res;
let next = [root];
while (next.length > 0) {
next = tr(res, next);
}
return res;
};
function tr(res, nodeArr) {
const arr = [];
const nextLevelNodes = [];
for (let i = 0; i < nodeArr.length; i++) {
arr.push(nodeArr[i].val);
if (nodeArr[i].left) {
nextLevelNodes.push(nodeArr[i].left);
}
if (nodeArr[i].right) {
nextLevelNodes.push(nodeArr[i].right);
}
}
if (arr.length) res.push(arr);
return nextLevelNodes;
}
Input
root = []
Output
[]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
q, res = [root], []
while any(q):
res.append([i.val for i in q])
q = [kid for node in q for kid in (node.left, node.right) if kid]
return res
Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]