題目描述
請實現(xiàn)一個函數(shù)按照之字形打印二叉樹玻侥，即第一行按照從左到右的順序打印篙顺，第二層按照從右至左的順序打印六孵，第三行按照從左到右的順序打印椿浓，其他行以此類推顽染。
思路
最初的思路是利用寬度優(yōu)先搜索，對樹進行層次遍歷轰绵。然后根據(jù)遍歷的層次來控制每次輸出的方向粉寞。比如奇數(shù)（假設(shè)從1開始）正向輸出，偶數(shù)反向輸出左腔。
后續(xù)做了一點改進唧垦，省去了逆向輸出這個操作。在層次遍歷的時候液样，先判斷當(dāng)前是應(yīng)該正向還是反向輸出的層振亮。如果是反向輸出巧还，那么把當(dāng)前層的當(dāng)前節(jié)點每次都插入到當(dāng)前隊列的最前面。這樣可以保證坊秸，當(dāng)遍歷完這一層時麸祷，存在數(shù)組里的節(jié)點已經(jīng)是逆向的。
代碼
class Solution:
def Print(self, pRoot):
if pRoot is None:
return []
result = []
q = [pRoot]
flag = 1 #控制輸出方向
while q:
current_level = []
temp_result = []
for node in q:
if flag == 1:
temp_result.append(node.val)
if flag == -1:
temp_result.insert(0,node.val) #把后續(xù)節(jié)點插入到起始部位
if node.left is not None:
current_level.append(node.left)
if node.right is not None:
current_level.append(node.right)
result.append(temp_result)
q = current_level
flag = flag * -1 #反向
return result
