題目描述
從上到下按層打印二叉樹，同一層結(jié)點(diǎn)從左至右輸出。每一層輸出一行。
知識(shí)點(diǎn)
二叉樹，隊(duì)列
Qiang的思路
這道題和面試題32.1相比理肺，多了分行輸出這個(gè)要求。在上一題的基礎(chǔ)上禁漓，這個(gè)也很簡單實(shí)現(xiàn)。因?yàn)槿绻覀冊诟?jié)點(diǎn)后面添加一個(gè)行結(jié)束的標(biāo)志位孵睬，那么當(dāng)該行全部遍歷完之后播歼，我們只需要把該標(biāo)志位放到隊(duì)列的最末端，這樣就相當(dāng)于在第二行最后面又多了一個(gè)標(biāo)志位掰读，那么便可以區(qū)分什么時(shí)候需要換行了荚恶。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二維列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if pRoot==None:
return []
result=[]
l=['#', pRoot]
while l!=['#']:
c=l.pop(0)
if c=='#':
result.append([])
l.append('#')
continue
result[-1].append(c.val)
if c.left!=None:
l.append(c.left)
if c.right!=None:
l.append(c.right)
return result
因?yàn)槲倚枰袛嗍裁磿r(shí)候給數(shù)組增加新行，所以我將標(biāo)志位放在了行前而不是行后磷支。這個(gè)并不影響解題的思路谒撼。
需要注意的是，標(biāo)志位會(huì)一直存在在隊(duì)列中雾狈，所以最終的遍歷終止條件是當(dāng)隊(duì)列中只有標(biāo)志位時(shí)廓潜。
Book中的思路
書中對于該題的處理也是在上一題的基礎(chǔ)上，增加了兩個(gè)變量解決的善榛，一個(gè)存儲(chǔ)著當(dāng)前行剩余的節(jié)點(diǎn)數(shù)辩蛋，另一個(gè)變量存儲(chǔ)著下一行的節(jié)點(diǎn)數(shù)。這樣便可以知道還需要輸出多少節(jié)點(diǎn)才能換行移盆，同時(shí)在換行時(shí)將開始下一行節(jié)點(diǎn)數(shù)的計(jì)數(shù)悼院。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二維列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
res=[[]]
l=[pRoot]
c_number=1
n_number=0
while len(l)!=0:
n=l.pop(0)
res[-1].append(n.val)
c_number-=1
if n.left!=None:
l.append(n.left)
n_number+=1
if n.right!=None:
l.append(n.right)
n_number+=1
if c_number==0 and n_number!=0:
c_number=n_number
n_number=0
res.append([])
return res
作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com咒循。
個(gè)人網(wǎng)站：https://www.myqiang.top据途。
