劍指offer 面試32題

面試32題：

題目：從上到下打印二叉樹

題：不分行從上到下打印二叉樹

解題代碼：

# -*- 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 hereif not root: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

?

題目拓展一：分行從上到下打印二叉樹。

題：從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。

解題代碼一：同劍指offer

# -*- 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 hereif not pRoot:return []res=[]res_val=[]res.append(pRoot)nextLevel=0 #表示下一層節點的數目toBePrinted=1 #表示當前層還沒有打印的節點數temp=[]while len(res)>0:node=res[0]temp.append(node.val)if node.left:res.append(node.left)nextLevel+=1if node.right:res.append(node.right)nextLevel+=1del res[0]toBePrinted-=1if toBePrinted==0:res_val.append(temp)toBePrinted=nextLevelnextLevel=0temp=[]return res_val

解題代碼二：代碼更簡潔。

# -*- 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 hereif not pRoot:return []res,nodes=[],[pRoot]while nodes:curStack,nextStack=[],[]for node in nodes:curStack.append(node.val)if node.left:nextStack.append(node.left)if node.right:nextStack.append(node.right)res.append(curStack)nodes=nextStackreturn res

?解題代碼三：cur、last記錄，思路同二

# -*- 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 hereif not pRoot:return []res=[]arr=[]arr.append(pRoot)cur=0#last=1while cur<len(arr):last=len(arr)temp=[]while (cur<last):temp.append(arr[cur].val)if arr[cur].left:arr.append(arr[cur].left)if arr[cur].right:arr.append(arr[cur].right)cur+=1res.append(temp)return res

?

?

題目拓展二：之字形打印二叉樹

題：請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推。

解題代碼一：簡潔。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def Print(self, pRoot):# write code hereif not pRoot:return []res=[]nodes=[pRoot]leftToRight=Truewhile nodes:curStack,nextStack=[],[]for node in nodes:curStack.append(node.val)if node.left:nextStack.append(node.left)if node.right:nextStack.append(node.right)if not leftToRight:curStack.reverse()res.append(curStack)leftToRight = not leftToRightnodes=nextStack

解題代碼二：同劍指offer。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:def Print(self, pRoot):# write code hereif not pRoot:return []res=[]nodes=[pRoot]right=Truewhile nodes:curStack,nextStack=[],[]if right:for node in nodes:curStack.append(node.val)if node.left:nextStack.append(node.left)if node.right:nextStack.append(node.right)else:for node in nodes:curStack.append(node.val)if node.right:nextStack.append(node.right)if node.left:nextStack.append(node.left)res.append(curStack)nextStack.reverse()right=not rightnodes=nextStackreturn res

?