lzyprime 博客 (github)
創(chuàng)建時間：2020.12.22
qq及郵箱：2383518170
leetcode 筆記
題目描述：
給定一個二叉樹选脊，返回其節(jié)點值的鋸齒形層序遍歷刻坊。（即先從左往右，再從右往左進行下一層遍歷权逗，以此類推，層與層之間交替進行）启盛。
例如：
給定二叉樹 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回鋸齒形層序遍歷如下：
[
[3],
[20,9],
[15,7]
]
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有姊氓。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處蟀伸。
code
二叉樹的層次遍歷蚀同。
至于從前往后還是從后往前讀，無非是個下標(biāo)的問題啊掏。開一個和當(dāng)前層等長的數(shù)組蠢络，如果從后往前讀則下標(biāo)倒序，把當(dāng)前層的val插入到數(shù)組里迟蜜。
-
c++
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if(root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode *> q;
q.push(root);
bool reverse = false;
while(!q.empty()) {
int len = q.size();
vector<int> tmp(len, 0);
for(int i = 0; i < len; i++) {
root = q.front();
q.pop();
tmp[reverse ? len - i - 1 : i] = root -> val;
if(root -> left != nullptr) q.push(root -> left);
if(root -> right != nullptr) q.push(root -> right);
}
ans.push_back(move(tmp));
reverse = !reverse;
}
return ans;
}
};
函數(shù)式語言里, 利用flatMap可以很容易的拿到下一層節(jié)點組成的集合, map得到當(dāng)前層節(jié)點val的集合刹孔。
-
kotlin
尾遞歸函數(shù) tailrec fun zigzagLevelOrder:
ans: List<List<Int>> : 當(dāng)前的累計結(jié)果
list: List<TreeNode> : 當(dāng)前層節(jié)點。
reverse: Boolean : 是否要倒序
如果當(dāng)前層沒有節(jié)點, 說明到底了, 返回ans; 否則娜睛， ans + 當(dāng)前層節(jié)點val的集合 作為新的累計結(jié)果髓霞， list.flatMap{ it -> listOfNotNull(it.left, it.right) } 得到下一層非空節(jié)點的集合卦睹， 開始調(diào)用下一層
所以可以一行， 一刀流方库。
tailrec fun zigzagLevelOrder(ans: List<List<Int>>, list: List<TreeNode>, reverse: Boolean): List<List<Int>> = if (list.isEmpty()) ans else zigzagLevelOrder(ans + listOf(list.map { it.`val` }.let { if (reverse) it.asReversed() else it }), list.flatMap { listOfNotNull(it.left, it.right) }, !reverse)
class Solution {
fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {
root ?: return emptyList()
tailrec fun zigzagLevelOrder(ans: List<List<Int>>, list: List<TreeNode>, reverse: Boolean): List<List<Int>> =
if (list.isEmpty()) ans
else
zigzagLevelOrder(
ans + listOf(list.map { it.`val` }.let { if (reverse) it.asReversed() else it }),
list.flatMap { listOfNotNull(it.left, it.right) },
!reverse
)
return zigzagLevelOrder(emptyList(), listOf(root), false)
}
}
-
scala
一刀流
@tailrec
def zigzagLevelOrder(ans: List[List[Int]], list: List[TreeNode], reverse: Boolean): List[List[Int]] = if (list.isEmpty) ans else zigzagLevelOrder(ans ::: List(if (reverse) list.map(_.value).reverse else list.map(_.value)) ::: Nil, list flatMap (it => it.left :: it.right :: Nil) filter (_ != null), !reverse)
/**
* Definition for a binary tree node.
* class TreeNode(var _value: Int) {
* var value: Int = _value
* var left: TreeNode = null
* var right: TreeNode = null
* }
*/
import scala.annotation.tailrec
object Solution {
def zigzagLevelOrder(root: TreeNode): List[List[Int]] = {
if (root == null) return Nil
@tailrec
def zigzagLevelOrder(ans: List[List[Int]], list: List[TreeNode], reverse: Boolean): List[List[Int]] =
if (list.isEmpty) ans
else
zigzagLevelOrder(
ans ::: List(if (reverse) list.map(_.value).reverse else list.map(_.value)) ::: Nil,
list flatMap (it => it.left :: it.right :: Nil) filter (_ != null),
!reverse
)
zigzagLevelOrder(Nil, List(root), reverse = false)
}
}
- rust
這種數(shù)據(jù)結(jié)構(gòu)題用 Rust 很不地道结序。尤其是一刀流，會比普通寫法還長纵潦，函數(shù)棧的原因要多耗點內(nèi)存徐鹤。算法復(fù)雜度相同的話，兩種寫法耗時不會有差距
// 一刀流 花括號不能省邀层，導(dǎo)致很長
impl Solution {
pub fn zigzag_level_order(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Vec<i32>> {
if let Some(i) = root {
fn zigzag_level_order(
mut ans: Vec<Vec<i32>>,
cur: Vec<Rc<RefCell<TreeNode>>>,
reverse: bool,
) -> Vec<Vec<i32>> {
if cur.is_empty() {
ans
} else {
zigzag_level_order(
{
let tmp = cur.iter().map(|i| i.borrow().val);
ans.push(if reverse {
tmp.rev().collect()
} else {
tmp.collect()
});
ans
},
cur.iter().fold(vec![], |mut acc, i| {
if let Some(ref left) = i.borrow().left {
acc.push(left.clone())
}
if let Some(ref right) = i.borrow().right {
acc.push(right.clone())
}
acc
}),
!reverse,
)
}
}
zigzag_level_order(vec![], vec![i], false)
} else {
vec![]
}
}
}
