題目描述
遞歸實作
遞歸實作主要是在函數内部定義一個新的函數,這個函數接收兩個參數,一個是目前節點,一個是層次,如果目前節點為空的話,則傳回空,如果目前節點不為空,判斷二維數組的指定位置是否為空,如果存在則push進目前節點的val值,如果不存在則設定為空數組,然後遞歸周遊左子樹,層次+1,遞歸周遊右子樹的時候層次還是+1。
var levelOrder = function(root) {
// 定義最終的傳回結果
const res = [];
function levelOrder(root,level) {
if (!root) return null;
res[level] = res[level] || [];
res[level].push(root.val);
levelOrder(root.left,level + 1);
levelOrder(root.right,level + 1);
};
levelOrder(root,0);
return res;
};
複制代碼
非遞歸實作
非遞歸實作主要是借助隊列來實作,首先擷取隊列中對應二叉樹的一層的元素,然後取出隊頭元素插入指定二維數組中,如果左子樹存在的話,讓左子樹入隊列,如果右子樹存在,則讓右子樹入隊列,循環完一層隊列的層次+1。
var levelOrder = function(root) {
if (!root) return []
// 定義最終的傳回結果
const res = [];
// 定義隊列
const queue = [root];
// 定義層次
let level = 0;
// 隻要隊列中有元素,便進入循環
while (queue.length) {
res.push([]);
let len = queue.length;
for (let i = 0; i < len; i++) {
// 取出對頭元素
let node = queue.shift();
res[level].push(node.val);
// 左子樹存在的話,讓左子樹入隊列
node.left && queue.push(node.left);
// 右子樹存在的話,讓右子樹入隊列
node.right && queue.push(node.right);
}
level++;
}
return res;
};
複制代碼
題目反思
二叉樹的層序周遊是一種非常重要的周遊方式,是我們必須掌握的,本題中值得我們學習的思路有以下幾點。
- 使用遞歸的層序周遊和使用疊代的層序周遊都需要借助層數level這個變量。
- 遞歸的思想和隊列的思想值得我們學習。