劍指Offer32-3. 從上到下列印二叉樹III
JavaScript劍指Offer題解
🚀包含陣列、物件、鏈表、堆疊、樹等經典題型
??每天一道，輕松不累
💬詳細的題目決議，收藏方便閱讀
🙏在線star地址
在線閱讀地址
在線閱讀地址
題目描述
請實作一個函式按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推，
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
回傳其層次遍歷結果：
[
[3],
[20,9],
[15,7]
]
題解一：BFS
思路
- 一次讀取一個節點，保存下一層節點
- 但利用每一層的數量，但需要利用層數的奇偶行反轉資料
/**
* @param {TreeNode} root
* @return {number[]}
*/
var levelOrder = function(root) {
if(root == null ) return [];
let res = [];
let queue = [];
queue.push(root);
let level = 0; // 層數
while(queue.length>0){ // 每一輪即為一層
let tmp = [];
let len = queue.length; // 當前層的節點個數
level++;
for(let i=0;i<len;i++){
let cur = queue.shift();
tmp.push(cur.val);
if(cur.left){
queue.push(cur.left)
}
if(cur.right){
queue.push(cur.right)
}
}
if(level%2 ===0){ // 偶數層將陣列逆序
tmp.reverse();
}
res.push(tmp)
}
return res;
};
寫在最后
本篇是劍指Offer的第14題，俗話說好的合理的資料結構+演算法才是寫好代碼的關鍵，不妨跟我一起來吧～
熱門開源專案
- 前端進階指南
- 高頻經典手撕代碼實作
- 劍指Offer題解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/339181.html
標籤：其他
下一篇：vue 實作 全選功能