Skip to content

Commit bbd169a

Browse files
yanglbmeyanglbme
authored
feat: add solutions to lc problem: No.0102 (doocs#2342)
No.0102.Binary Tree Level Order Traversal
1 parent 010041b commit bbd169a

File tree

6 files changed

+147
-141
lines changed

6 files changed

+147
-141
lines changed

‎solution/0100-0199/0102.Binary Tree Level Order Traversal/README.md

Lines changed: 49 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -148,8 +148,12 @@ public:
148148
auto node = q.front();
149149
q.pop();
150150
t.push_back(node->val);
151-
if (node->left) q.push(node->left);
152-
if (node->right) q.push(node->right);
151+
if (node->left) {
152+
q.push(node->left);
153+
}
154+
if (node->right) {
155+
q.push(node->right);
156+
}
153157
}
154158
ans.push_back(t);
155159
}
@@ -207,23 +211,23 @@ func levelOrder(root *TreeNode) (ans [][]int) {
207211
*/
208212

209213
function levelOrder(root: TreeNode | null): number[][] {
210-
const res = [];
211-
if (root == null) {
212-
return res;
214+
const ans: number[][] = [];
215+
if (!root) {
216+
return ans;
213217
}
214-
const queue = [root];
215-
while (queue.length != 0) {
216-
const n = queue.length;
217-
res.push(
218-
new Array(n).fill(null).map(() => {
219-
const { val, left, right } = queue.shift();
220-
left && queue.push(left);
221-
right && queue.push(right);
222-
return val;
223-
}),
224-
);
218+
const q: TreeNode[] = [root];
219+
while (q.length) {
220+
const t: number[] = [];
221+
const qq: TreeNode[] = [];
222+
for (const { val, left, right } of q) {
223+
t.push(val);
224+
left && qq.push(left);
225+
right && qq.push(right);
226+
}
227+
ans.push(t);
228+
q.splice(0, q.length, ...qq);
225229
}
226-
return res;
230+
return ans;
227231
}
228232
```
229233

@@ -248,34 +252,31 @@ function levelOrder(root: TreeNode | null): number[][] {
248252
// }
249253
use std::rc::Rc;
250254
use std::cell::RefCell;
251-
use std::collections::VecDeque;
255+
use std::collections::{ VecDeque };
252256
impl Solution {
253257
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
254-
let mut res = vec![];
255-
if root.is_none() {
256-
return res;
257-
}
258-
let mut queue: VecDeque<Option<Rc<RefCell<TreeNode>>>> = vec![root].into_iter().collect();
259-
while !queue.is_empty() {
260-
let n = queue.len();
261-
res.push(
262-
(0..n)
263-
.into_iter()
264-
.map(|_| {
265-
let mut node = queue.pop_front().unwrap();
266-
let mut node = node.as_mut().unwrap().borrow_mut();
267-
if node.left.is_some() {
268-
queue.push_back(node.left.take());
258+
let mut ans = Vec::new();
259+
if let Some(root_node) = root {
260+
let mut q = VecDeque::new();
261+
q.push_back(root_node);
262+
while !q.is_empty() {
263+
let mut t = Vec::new();
264+
for _ in 0..q.len() {
265+
if let Some(node) = q.pop_front() {
266+
let node_ref = node.borrow();
267+
t.push(node_ref.val);
268+
if let Some(ref left) = node_ref.left {
269+
q.push_back(Rc::clone(left));
269270
}
270-
if node.right.is_some() {
271-
queue.push_back(node.right.take());
271+
if let Some(ref right) = node_ref.right {
272+
q.push_back(Rc::clone(right));
272273
}
273-
node.val
274-
})
275-
.collect()
276-
);
274+
}
275+
}
276+
ans.push(t);
277+
}
277278
}
278-
res
279+
ans
279280
}
280281
}
281282
```
@@ -294,20 +295,21 @@ impl Solution {
294295
* @return {number[][]}
295296
*/
296297
var levelOrder = function (root) {
297-
let ans = [];
298+
const ans = [];
298299
if (!root) {
299300
return ans;
300301
}
301-
let q = [root];
302+
const q = [root];
302303
while (q.length) {
303-
let t = [];
304-
for (let n = q.length; n; --n) {
305-
const { val, left, right } = q.shift();
304+
const t = [];
305+
const qq = [];
306+
for (const { val, left, right } of q) {
306307
t.push(val);
307-
left && q.push(left);
308-
right && q.push(right);
308+
left && qq.push(left);
309+
right && qq.push(right);
309310
}
310311
ans.push(t);
312+
q.splice(0, q.length, ...qq);
311313
}
312314
return ans;
313315
};

‎solution/0100-0199/0102.Binary Tree Level Order Traversal/README_EN.md

Lines changed: 49 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -144,8 +144,12 @@ public:
144144
auto node = q.front();
145145
q.pop();
146146
t.push_back(node->val);
147-
if (node->left) q.push(node->left);
148-
if (node->right) q.push(node->right);
147+
if (node->left) {
148+
q.push(node->left);
149+
}
150+
if (node->right) {
151+
q.push(node->right);
152+
}
149153
}
150154
ans.push_back(t);
151155
}
@@ -203,23 +207,23 @@ func levelOrder(root *TreeNode) (ans [][]int) {
203207
*/
204208

205209
function levelOrder(root: TreeNode | null): number[][] {
206-
const res = [];
207-
if (root == null) {
208-
return res;
210+
const ans: number[][] = [];
211+
if (!root) {
212+
return ans;
209213
}
210-
const queue = [root];
211-
while (queue.length != 0) {
212-
const n = queue.length;
213-
res.push(
214-
new Array(n).fill(null).map(() => {
215-
const { val, left, right } = queue.shift();
216-
left && queue.push(left);
217-
right && queue.push(right);
218-
return val;
219-
}),
220-
);
214+
const q: TreeNode[] = [root];
215+
while (q.length) {
216+
const t: number[] = [];
217+
const qq: TreeNode[] = [];
218+
for (const { val, left, right } of q) {
219+
t.push(val);
220+
left && qq.push(left);
221+
right && qq.push(right);
222+
}
223+
ans.push(t);
224+
q.splice(0, q.length, ...qq);
221225
}
222-
return res;
226+
return ans;
223227
}
224228
```
225229

@@ -244,34 +248,31 @@ function levelOrder(root: TreeNode | null): number[][] {
244248
// }
245249
use std::rc::Rc;
246250
use std::cell::RefCell;
247-
use std::collections::VecDeque;
251+
use std::collections::{ VecDeque };
248252
impl Solution {
249253
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
250-
let mut res = vec![];
251-
if root.is_none() {
252-
return res;
253-
}
254-
let mut queue: VecDeque<Option<Rc<RefCell<TreeNode>>>> = vec![root].into_iter().collect();
255-
while !queue.is_empty() {
256-
let n = queue.len();
257-
res.push(
258-
(0..n)
259-
.into_iter()
260-
.map(|_| {
261-
let mut node = queue.pop_front().unwrap();
262-
let mut node = node.as_mut().unwrap().borrow_mut();
263-
if node.left.is_some() {
264-
queue.push_back(node.left.take());
254+
let mut ans = Vec::new();
255+
if let Some(root_node) = root {
256+
let mut q = VecDeque::new();
257+
q.push_back(root_node);
258+
while !q.is_empty() {
259+
let mut t = Vec::new();
260+
for _ in 0..q.len() {
261+
if let Some(node) = q.pop_front() {
262+
let node_ref = node.borrow();
263+
t.push(node_ref.val);
264+
if let Some(ref left) = node_ref.left {
265+
q.push_back(Rc::clone(left));
265266
}
266-
if node.right.is_some() {
267-
queue.push_back(node.right.take());
267+
if let Some(ref right) = node_ref.right {
268+
q.push_back(Rc::clone(right));
268269
}
269-
node.val
270-
})
271-
.collect()
272-
);
270+
}
271+
}
272+
ans.push(t);
273+
}
273274
}
274-
res
275+
ans
275276
}
276277
}
277278
```
@@ -290,20 +291,21 @@ impl Solution {
290291
* @return {number[][]}
291292
*/
292293
var levelOrder = function (root) {
293-
let ans = [];
294+
const ans = [];
294295
if (!root) {
295296
return ans;
296297
}
297-
let q = [root];
298+
const q = [root];
298299
while (q.length) {
299-
let t = [];
300-
for (let n = q.length; n; --n) {
301-
const { val, left, right } = q.shift();
300+
const t = [];
301+
const qq = [];
302+
for (const { val, left, right } of q) {
302303
t.push(val);
303-
left && q.push(left);
304-
right && q.push(right);
304+
left && qq.push(left);
305+
right && qq.push(right);
305306
}
306307
ans.push(t);
308+
q.splice(0, q.length, ...qq);
307309
}
308310
return ans;
309311
};

‎solution/0100-0199/0102.Binary Tree Level Order Traversal/Solution.cpp

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,8 +21,12 @@ class Solution {
2121
auto node = q.front();
2222
q.pop();
2323
t.push_back(node->val);
24-
if (node->left) q.push(node->left);
25-
if (node->right) q.push(node->right);
24+
if (node->left) {
25+
q.push(node->left);
26+
}
27+
if (node->right) {
28+
q.push(node->right);
29+
}
2630
}
2731
ans.push_back(t);
2832
}

‎solution/0100-0199/0102.Binary Tree Level Order Traversal/Solution.js

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -11,20 +11,21 @@
1111
* @return {number[][]}
1212
*/
1313
var levelOrder = function (root) {
14-
let ans = [];
14+
const ans = [];
1515
if (!root) {
1616
return ans;
1717
}
18-
let q = [root];
18+
const q = [root];
1919
while (q.length) {
20-
let t = [];
21-
for (let n = q.length; n; --n) {
22-
const { val, left, right } = q.shift();
20+
const t = [];
21+
const qq = [];
22+
for (const { val, left, right } of q) {
2323
t.push(val);
24-
left && q.push(left);
25-
right && q.push(right);
24+
left && qq.push(left);
25+
right && qq.push(right);
2626
}
2727
ans.push(t);
28+
q.splice(0, q.length, ...qq);
2829
}
2930
return ans;
3031
};

‎solution/0100-0199/0102.Binary Tree Level Order Traversal/Solution.rs

Lines changed: 20 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -18,33 +18,30 @@
1818
// }
1919
use std::rc::Rc;
2020
use std::cell::RefCell;
21-
use std::collections::VecDeque;
21+
use std::collections::{ VecDeque };
2222
impl Solution {
2323
pub fn level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
24-
let mut res = vec![];
25-
if root.is_none() {
26-
return res;
27-
}
28-
let mut queue: VecDeque<Option<Rc<RefCell<TreeNode>>>> = vec![root].into_iter().collect();
29-
while !queue.is_empty() {
30-
let n = queue.len();
31-
res.push(
32-
(0..n)
33-
.into_iter()
34-
.map(|_| {
35-
let mut node = queue.pop_front().unwrap();
36-
let mut node = node.as_mut().unwrap().borrow_mut();
37-
if node.left.is_some() {
38-
queue.push_back(node.left.take());
24+
let mut ans = Vec::new();
25+
if let Some(root_node) = root {
26+
let mut q = VecDeque::new();
27+
q.push_back(root_node);
28+
while !q.is_empty() {
29+
let mut t = Vec::new();
30+
for _ in 0..q.len() {
31+
if let Some(node) = q.pop_front() {
32+
let node_ref = node.borrow();
33+
t.push(node_ref.val);
34+
if let Some(ref left) = node_ref.left {
35+
q.push_back(Rc::clone(left));
3936
}
40-
if node.right.is_some() {
41-
queue.push_back(node.right.take());
37+
if let Some(ref right) = node_ref.right {
38+
q.push_back(Rc::clone(right));
4239
}
43-
node.val
44-
})
45-
.collect()
46-
);
40+
}
41+
}
42+
ans.push(t);
43+
}
4744
}
48-
res
45+
ans
4946
}
5047
}

0 commit comments

Comments
 (0)