Algorithm
Problem Nmae: 107. Binary Tree Level Order Traversal II
problem Link: https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
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:
Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]
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
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, struct TreeNode **queue, int n, int *c, int d) {
int *buff, buffsz, newqsz, k, i;
struct TreeNode *node, **newq;
buffsz = 10;
buff = malloc(buffsz * sizeof(int));
newqsz = 10;
newq = malloc(newqsz * sizeof(struct TreeNode *));
//assert(buff && new_p);
k = 0;
for (i = 0; i < n; i ++) {
node = queue[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 (k + 1 >= newqsz) {
newqsz *= 2;
newq = realloc(newq, newqsz * sizeof(struct TreeNode *));
//assert(newq);
}
if (node->left) newq[k ++] = node->left;
if (node->right) newq[k ++] = node->right;
}
//printf("done!\n");
free(queue);
p[d] = buff;
if (k) bfs(p, newq, k, c, d - 1);
else free(newq);
}
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize) {
int d, n;
int **p, *c;
struct TreeNode **queue;
*returnSize = 0;
if (!root) return NULL;
d = depth(root);
p = malloc(d * sizeof(int *));
c = calloc(d, sizeof(int));
queue = malloc(1 * sizeof(struct TreeNode *));
//assert(p && q);
n = 0;
queue[n ++] = root;
bfs(p, queue, n, c, d - 1);
*returnSize = d;
*columnSizes = c;
return p;
}
Input
root = [3,9,20,null,null,15,7]
Output
[[15,7],[9,20],[3]]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector < vector<int>>v;
dfs(root, v, 0);
reverse(v.begin(), v.end());
return v;
}
void dfs(TreeNode* root, vector < vector<int>>& v, int level){
if(!root) return;
if(level == v.size()) v.push_back({});
v[level].push_back(root->val);
dfs(root->left, v, level + 1);
dfs(root->right, v, level + 1);
}
};
Input
root = [3,9,20,null,null,15,7]
Output
[[15,7],[9,20],[3]]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const levelOrderBottom = function(root) {
const levels = []
postOrderTraversal(root)
return levels.reverse()
function postOrderTraversal(node, level = 0) {
if (node) {
if (!levels[level]) levels.push([])
postOrderTraversal(node.left, level + 1)
postOrderTraversal(node.right, level + 1)
levels[level].push(node.val)
}
}
}
Input
root = [1]
Output
[[1]]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
from collections import deque
if root is None:
return []
levels=list()
q=deque([root])
levels.append([i.val for i in q])
target=root
while q:
node=q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
if node==target:
if q:
levels.append([i.val for i in q])
target=q[-1]
return list(reversed(levels))
Input
root = [1]
Output
[[1]]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _107_BinaryTreeLevelOrderTraversal2
{
private Queue < TreeNode> queue = new Queue();
public IList 0)
{
var result = new List < int>();
var levelSize = queue.Count;
for (int i = 0; i < levelSize; i++)
{
var node = queue.Dequeue();
result.Add(node.val);
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}
results.Add(result);
}
results.Reverse();
return results;
}
}
}
Input
root = []
Output
[]