二叉樹的鋸齒形層序遍歷

題目描述：給定一個(gè)二叉樹，返回其節(jié)點(diǎn)值的鋸齒形層序遍歷。（即先從左往右，再?gòu)挠彝筮M(jìn)行下一層遍歷，以此類推，層與層之間交替進(jìn)行）。

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：利用隊(duì)列和棧遍歷二叉樹

隊(duì)列的特點(diǎn)是先進(jìn)先出，棧的特點(diǎn)是后進(jìn)先出，所以利用隊(duì)列和棧來遍歷二叉樹實(shí)現(xiàn)鋸齒形遍歷，具體過程如下：

• 首先，如果root為空，直接返回空的List。

• 如果root不為空，聲明一個(gè)隊(duì)列nodes，將root節(jié)點(diǎn)加入到隊(duì)列中，聲明一個(gè)result，聲明一個(gè)boolean類型的變量directionFlag，當(dāng)directionFlag為true時(shí)，從左往右往棧中放入節(jié)點(diǎn)；當(dāng)directionFlag為false時(shí)，從右往左放入節(jié)點(diǎn)，然后遍歷nodes中的節(jié)點(diǎn)，遍歷過程如下：

• 首先，用count記錄當(dāng)前隊(duì)列中節(jié)點(diǎn)的數(shù)量，即為當(dāng)前層節(jié)點(diǎn)的數(shù)量，vals記錄當(dāng)前節(jié)點(diǎn)的值，聲明一個(gè)棧temp；

• 從nodes中按順序取出count個(gè)節(jié)點(diǎn)，并且將相應(yīng)的節(jié)點(diǎn)值放入vals中，同時(shí)如果當(dāng)前節(jié)點(diǎn)的左右子節(jié)點(diǎn)不為空，根據(jù)directionFlag判斷是按從左到右的順序還是從右往左的順序放入temp中。然后將vals加入到結(jié)果result中。

• 將棧temp中的元素全部取出放入nodes。

• 重復(fù)遍歷nodes中的節(jié)點(diǎn)，直到nodes為空。

• 最后返回result即為鋸齒形層序遍歷的結(jié)果。

說明：解決方法類似 LeetCode-102-二叉樹的層序遍歷。

【每日寄語(yǔ)】 學(xué)習(xí)的敵人是自己的滿足，要認(rèn)真學(xué)習(xí)一點(diǎn)東西，必須從不自滿開始！