| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (57.54%) | 752 | - |
Tags
stack | tree | breadth-first-search
Companies
bloomberg | linkedin | microsoft
给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1：
1
2
| 输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]
|
示例 2：
1
2
| 输入：root = [1]
输出：[[1]]
|
示例 3：
提示：
- 树中节点数目在范围
[0, 2000] 内 -100 <= Node.val <= 100
Discussion | Solution
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
| // @lc code=start
// 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::cell::RefCell;
use std::rc::Rc;
impl Solution {
/// ## 解题思路
/// - 队列
pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
let mut res = vec![];
if root.is_none() {
return res;
}
let mut reverse_dir = true;
let mut queue = Vec::new();
let mut tmp = Vec::new();
queue.push(root.clone().unwrap());
while !queue.is_empty() {
let mut vals = Vec::new();
while let Some(node) = queue.pop() {
let node = node.borrow();
vals.push(node.val);
match reverse_dir {
true => {
node.left.clone().map(|n| tmp.push(n));
node.right.clone().map(|n| tmp.push(n));
}
_ => {
node.right.clone().map(|n| tmp.push(n));
node.left.clone().map(|n| tmp.push(n));
}
}
}
reverse_dir = !reverse_dir;
res.push(vals);
std::mem::swap(&mut queue, &mut tmp);
}
res
}
}
// @lc code=end
|