資訊專欄INFORMATION COLUMN
摘要：題目描述請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推分析第一反應(yīng)可以按照普通的層次遍歷然后再把第等等偶數(shù)層的結(jié)果翻轉(zhuǎn)一下，但是那樣子效率太低。
題目描述
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形打印二叉樹(shù)，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推
分析第一反應(yīng)可以按照普通的層次遍歷然后再把第2、4、6等等偶數(shù)層的結(jié)果翻轉(zhuǎn)一下，但是那樣子效率太低。
上網(wǎng)查閱可以使用雙向隊(duì)列，即兩頭都可以進(jìn)和出。需要從左到右打印的從隊(duì)列頭部進(jìn)入和彈出，需要從右往左打印的從隊(duì)列尾部進(jìn)入和彈出
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(r)
{
if(r === null)
return [];
var ds = [];
var dir = "r";
var res = [];
ds.unshift(null);
ds.unshift(r);
while(ds.length > 1) {
var temp = [];
if(dir === "r"){
var cur = ds.shift();
while(cur !== null) {
temp.push(cur.val);
if(cur.left !== null)
ds.push(cur.left);
if(cur.right !== null)
ds.push(cur.right)
cur = ds.shift();
}
ds.unshift(null);
}else{
var cur = ds.pop();
while(cur !== null){
temp.push(cur.val);
if(cur.right !== null)
ds.unshift(cur.right);
if(cur.left !== null)
ds.unshift(cur.left);
cur = ds.pop();
}
ds.push(null);
}
res.push(temp);
dir = dir === "r" ? "l" : "r";
}
return res;
}
module.exports = {
Print : Print
};
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/96178.html
摘要：題目描述從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。分析二叉樹(shù)的層次遍歷，可以借助隊(duì)列的幫助實(shí)現(xiàn) 題目描述 從上往下打印出二叉樹(shù)的每個(gè)節(jié)點(diǎn)，同層節(jié)點(diǎn)從左至右打印。 分析 二叉樹(shù)的層次遍歷，可以借助隊(duì)列的幫助 實(shí)現(xiàn) /* function TreeNode(x) { this.val = x; this.left = null; this.right =...
摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結(jié)遞歸終止的條件為碰到空節(jié)點(diǎn)。 目錄 分析二叉樹(shù)的前序，中序，后序的遍歷步驟 1.層序遍歷 方法一：廣度優(yōu)先搜索? (以下解釋來(lái)自leetcode官方題解) 方法...
摘要：題目描述輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。思路二叉樹(shù)的大多數(shù)問(wèn)題可以使用遞歸來(lái)解決，本題亦如此。 題目描述 輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。 思路 二叉樹(shù)的大多數(shù)問(wèn)題可以使用...
摘要：題目從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。分析分層次遍歷肯定要使用隊(duì)列來(lái)完成了，沒(méi)啥好分析的代碼實(shí)現(xiàn) 題目 從上到下按層打印二叉樹(shù)，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。 分析 分層次遍歷肯定要使用隊(duì)列來(lái)完成了，沒(méi)啥好分析的 代碼實(shí)現(xiàn) /* function TreeNode(x) { this.val = x; this.left = null; ...
閱讀 3776·2021-11-11 11:00
閱讀 2245·2021-10-08 10:05
閱讀 2943·2021-10-08 10:04
閱讀 3276·2021-09-30 09:48
閱讀 3970·2021-09-27 14:10
閱讀 1784·2021-09-09 09:33
閱讀 2185·2019-08-30 15:55
閱讀 1661·2019-08-30 13:53
