题目一：不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
解题思路：
总结规律为首先将根节点加入到队列中，然后当队列不为空时，打印队列首部的的节点值，如果该节点有左右节点则将左右节点加入队列的尾部，接着需要再将队列首部的元素取出，重复上述的打印操作。
代码实现：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root is None:
return [] #如果为空，直接返回空列表
#保存节点的缓存队列
res = []
res_val = []
res.append(root)
while len(res)>0:
Node = res.pop(0) #将队列头部的节点取出
res_val.append(Node.val)#加入打印的列表的尾端
if Node.left: #如果该节点有左节点将其加入队列尾端
res.append(Node.left)
if Node.right: #如果该节点有右节点将其加入队列尾端
res.append(Node.right)
return res_val #最终返回值列表
提交结果：
————————————————————————————————
题目二：
分行打印按照层次遍历的结果
解题思路：
这道题和上一题目思路一样，但是多了一个换行控制，将同一层的val添加到一个列表，当需要换行时把这一列表的值全部添加到打印列表，然后进行下一层的列表添加。为此需要引入两个变量，一个是当前层需要打印的节点数，一个是下一层的总节点数，当当前层次需要打印的节点数为0是进行当前层的列表添加操作并且进行变量更新以便于下层的打印。
代码实现：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
res = []
res_val = []
res.append(pRoot)
ToBePrint = 1 #根节点为一个节点
NextLevel = 0 #下一层的节点数
temp = [] #储存每层节点的变量
while len(res)>0:
node = res.pop(0)
temp.append(node.val)
ToBePrint -=1 #要打印的数目减1
if node.left:
res.append(node.left)
NextLevel+=1 #x下一层节点数加1
if node.right:
res.append(node.right)
NextLevel+=1
if ToBePrint ==0: #该层的节点数已经打印结束
res_val.append(temp)
ToBePrint = NextLevel #更新变量
NextLevel = 0
temp = []
return res_val
提交结果：
—————————————————————————————————
题目三：
之字型打印二叉树
思路：
这道题可以受上面题目二的启发，即在上述的条件下，再增加一个lefttoright的变量，初始化为true，一层打印结束之后，将lefttoright反转，当lefttoright到为真时，和上述一致，当为假时，将temp倒叙加入到列表中，具体如下：
32 之字形打印二叉树.png
代码实现：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def Print(self, pRoot):
# write code here
if pRoot == None:
return []
res = []
res_val = []
res.append(pRoot)
leftToright = True
ToBePrint = 1 #根节点为一个节点
NextLevel = 0 #下一层的节点数
temp = [] #储存每层节点的变量
while len(res)>0:
node = res.pop(0)
temp.append(node.val)
ToBePrint -=1 #要打印的数目减1
if node.left:
res.append(node.left)
NextLevel+=1 #x下一层节点数加1
if node.right:
res.append(node.right)
NextLevel+=1
if ToBePrint ==0: #该层的节点数已经打印结束
if leftToright:
res_val.append(temp)
else:
res_val.append(temp[::-1])
ToBePrint = NextLevel #更新变量
NextLevel = 0
temp = []
leftToright = not leftToright
return res_val
提交结果：
网友评论