## 107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7

return its bottom-up level order traversal as:

[
[15,7],
[9,20],
[3]
]

## Rust Solution

struct Solution;
use rustgym_util::*;
use std::collections::VecDeque;

struct Pair {
level: usize,
}

impl Solution {
fn level_order_bottom(root: TreeLink) -> Vec<Vec<i32>> {
let mut levels: Vec<Vec<i32>> = vec![];
let mut queue: VecDeque<Pair> = VecDeque::new();
if root.is_some() {
queue.push_back(Pair {
tree: root,
level: 0,
});
while let Some(pair) = queue.pop_front() {
let node = pair.tree.unwrap();
let mut node = node.borrow_mut();
let level = pair.level;
let val = node.val;
let left = node.left.take();
let right = node.right.take();
if let Some(group) = levels.get_mut(level) {
group.push(val);
} else {
let group = vec![val];
levels.insert(level, group);
}
if left.is_some() {
queue.push_back(Pair {
tree: left,
level: level + 1,
});
}
if right.is_some() {
queue.push_back(Pair {
tree: right,
level: level + 1,
});
}
}
}
levels.reverse();
levels
}
}

#[test]
fn test() {
let tree = tree!(3, tree!(9), tree!(20, tree!(15), tree!(7)));
let nodes = vec![vec![15, 7], vec![9, 20], vec![3]];
assert_eq!(Solution::level_order_bottom(tree), nodes);
}

Having problems with this solution? Click here to submit an issue on github.