-
Notifications
You must be signed in to change notification settings - Fork 1
/
binary-tree-level-order-traversal-ii.rs
60 lines (51 loc) · 1.45 KB
/
binary-tree-level-order-traversal-ii.rs
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::VecDeque;
struct Pair {
pub first: Rc<RefCell<TreeNode>>,
pub second: usize,
}
fn enq(cur: &Pair, q: &mut VecDeque<Pair>) {
if let Some(left) = &cur.first.borrow().left {
q.push_back(Pair{first: left.clone(), second: cur.second + 1});
}
if let Some(right) = &cur.first.borrow().right {
q.push_back(Pair{first: right.clone(), second: cur.second + 1});
}
}
impl Solution {
pub fn level_order_bottom(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut q: VecDeque<Pair> = VecDeque::new();
let mut ans: Vec<Vec<i32>> = Vec::new();
if let Some(r) = root {
q.push_back(Pair{first: r, second: 0})
}
while let Some(cur) = q.pop_front() {
enq(&cur, &mut q);
if (ans.len() <= cur.second) {
ans.push(Vec::new());
}
ans[cur.second].push(cur.first.borrow().val);
}
ans.reverse();
ans
}
}