??劍指 Offer 32 - III. 從上到下列印二叉樹 III??
請實作一個函式按照之字形順序列印二叉樹，即第一行按照從左到右的順序列印，第二層按照從右到左的順序列印，第三行再按照從左到右的順序列印，其他行以此類推，
例如:
給定二叉樹: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
回傳其層次遍歷結果：
[
[3],
[20,9],
[15,7]
]
提示：
節點總數 <= 1000
??分析??
陣列嵌套陣列，內層陣列為每一層的總結點數
思路：也是用佇列來解決，先判斷此時佇列長度(每一層的結點個數)，然后通過for回圈(長度為佇列長度)，彈出隊頭，壓入臨時陣列，左或右有子結點那就壓入佇列
(***)，
for回圈結束后可以保證該層全部結點已經壓入臨時陣列，再把該臨時陣列壓入回傳的陣列即可，
可以發現“for回圈為佇列長度”這個設計思想很精妙
代碼如下：
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return [];
let arr = [], queue = [], temp = [], node, len, flag = 1;
queue.push(root);
while(queue.length) {
temp = [];
len = queue.length;
for(let i=0; i<len; i++) {
node = queue.shift();
if(flag == 1)
temp.push(node.val);
else
temp.unshift(node.val);
if(node.left) {
queue.push(node.left);
}
if(node.right) {
queue.push(node.right);
}
}
arr.push(temp);
flag = !flag;
}
return arr;
};
演算法效率如圖：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/350973.html
標籤：其他
上一篇：劍指 Offer 27. 二叉樹的鏡像 javascript解法
下一篇：Vue-cli 環境搭建和使用