## Algorithm

Problem Nmae: 107. 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;
}
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
[[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);
}
};
``````
Copy The Code &

Input

cmd
root = [3,9,20,null,null,15,7]

Output

cmd
[[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)
}
}
}
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[[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))
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[[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();
if (node.left != null)
queue.Enqueue(node.left);
if (node.right != null)
queue.Enqueue(node.right);
}

}

results.Reverse();
return results;
}
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]