Skip to content

Commit f3acc6d

Browse files
committed
solve #102
1 parent 0877ba9 commit f3acc6d

File tree

2 files changed

+79
-0
lines changed

2 files changed

+79
-0
lines changed

src/lib.rs

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,3 +102,4 @@ mod n0098_validate_binary_search_tree;
102102
mod n0099_recover_binary_search_tree;
103103
mod n0100_same_tree;
104104
mod n0101_symmetric_tree;
105+
mod n0102_binary_tree_level_order_traversal;
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/**
2+
* [102] Binary Tree Level Order Traversal
3+
*
4+
* Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
5+
*
6+
*
7+
* For example:<br />
8+
* Given binary tree [3,9,20,null,null,15,7],<br />
9+
*
10+
* 3
11+
* / \
12+
* 9 20
13+
* / \
14+
* 15 7
15+
*
16+
*
17+
*
18+
* return its level order traversal as:<br />
19+
*
20+
* [
21+
* [3],
22+
* [9,20],
23+
* [15,7]
24+
* ]
25+
*
26+
*
27+
*/
28+
pub struct Solution {}
29+
use super::util::tree::{TreeNode, to_tree};
30+
31+
// submission codes start here
32+
33+
use std::rc::Rc;
34+
use std::cell::RefCell;
35+
use std::collections::VecDeque;
36+
impl Solution {
37+
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
38+
let mut res = Vec::new();
39+
let mut current_level = 0;
40+
if root.is_none() { return res }
41+
let mut deq = VecDeque::new();
42+
deq.push_back((0, root.clone()));
43+
let mut vec = Vec::new();
44+
while !deq.is_empty() {
45+
if let Some((level, Some(node))) = deq.pop_front() {
46+
deq.push_back((level+1, node.borrow().left.clone()));
47+
deq.push_back((level+1, node.borrow().right.clone()));
48+
if level > current_level {
49+
res.push(vec);
50+
vec = Vec::new();
51+
current_level = level;
52+
}
53+
vec.push(node.borrow().val);
54+
}
55+
}
56+
if !vec.is_empty() { res.push(vec) }
57+
res
58+
}
59+
}
60+
61+
// submission codes end
62+
63+
#[cfg(test)]
64+
mod tests {
65+
use super::*;
66+
67+
#[test]
68+
fn test_102() {
69+
assert_eq!(
70+
Solution::level_order(tree![3,9,20,null,null,15,7]),
71+
vec![
72+
vec![3],
73+
vec![9,20],
74+
vec![15,7]
75+
]
76+
);
77+
}
78+
}

0 commit comments

Comments
 (0)