層次周遊二叉樹（程式設計之美3.10）

問題（假定根節點位于第0層）

1. 層次周遊二叉樹（每層換行分開）

2. 層次周遊二叉樹指定的某層

例如

上圖中

1.

2.

可以看出得出第二問的解，第一問迎刃而解了，是以從問題二下手

分析與解

1. 層次周遊二叉樹指定的某層

可以得出這樣的一個結論：周遊二叉樹的第k層，相當于周遊二叉樹根節點的左右子樹的第k-1層。這樣一直周遊下去，直到k=0時，輸出節點即可。

參考代碼

<a></a>

完整執行代碼

 View Code

執行結果

2. 層次周遊二叉樹

解法1——根據求得的層次，周遊每一層

完整執行程式

解法2——無需求得層次，根據周遊每層的傳回資訊确定周遊

解法3——無需求每次都從根說起，一次周遊成功

可以看出，解法1、2每次都需要從根說起，還可以不從跟談起，一次周遊所有的節點，不過這需要額外的存儲空間

思路

定義兩個指針：cur、last.cur指向目前該通路的節點位置，last指向目前隊列中最後一個元素的後一個位置

周遊每一層時，周遊每一個元素是cur往後移動，同時把cur指向的左右孩子加入到隊列中，當cur==last時說明該層已經周遊完事了。

C語言寫的

之字形列印

例子：例子中列印

參考