總結(jié)一下二叉樹的深度遍歷(DFS)和廣度遍歷(BFS)
首先寝志， 創(chuàng)建二叉樹的節(jié)點：
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
一、深度遍歷
1.1 先序遍歷(根->左->右)
class Solution(object):
def preorderTraveral1(self, root):
"遞歸法"
q = []
def recur(root):
if root is None:
return None
q.append(root)
recur(root.left)
recur(root.right)
recur(root)
return q
def preorderTraveral2(self, root):
"""
迭代法：利用兩個stack來儲存節(jié)點滔灶。
當(dāng)遍歷開始時牧牢，將二叉樹左節(jié)點的元素依次放入output中纸兔，
同時用stack儲存每一個節(jié)點的右節(jié)點。當(dāng)左邊節(jié)點遍歷完
之后诸迟，從stack中依次取出右節(jié)點茸炒，放入output中，直到stack
中沒有節(jié)點阵苇，遍歷結(jié)束壁公。
"""
if root is None:
return []
stack = []
output = []
cur = root
while stack or cur:
if cur:
output.append(root.var)
stack.append(root.right)
cur = cur.left
else:
cur = stack.pop()
return output
1.2 中序遍歷(左->根->右)
class Solution(object):
def inorderTraveral1(self, root):
"遞歸法"
q = []
def recur(root):
if root == None:
return None
recur(root.left)
q.append(root.val)
recur(root.right)
recur(root)
return q
def inorderTraveral2(self, root):
"""
迭代法：利用兩個stack來儲存節(jié)點。
遍歷開始時绅项， 將左節(jié)點依次放入stack中暫時存儲紊册，
當(dāng)左節(jié)點為空時，從stack中取出一個節(jié)點放入output
中快耿， 然后檢查當(dāng)前節(jié)點的右節(jié)點囊陡，右節(jié)點不為空，
將其放入output中掀亥，否則繼續(xù)從stack中取出節(jié)點撞反，然
后循環(huán)遍歷，一直到stack中沒有節(jié)點為止搪花，循環(huán)結(jié)束
"""
if root is None:
return []
stack = []
output = []
cur = root
while cur or stack:
if cur:
stack.append(root)
cur = cur.left
else:
cur = stack.pop()
output.append(cur.var)
cur = cur.right
return output
1.3 后序遍歷(左->右->根)
class Solution(object):
def portorderTraveral1(self, root):
"遞歸法"
q = []
def recur(root):
if root == None:
return None
recur(root.left)
recur(root.right)
q.append(root.var)
recur(root)
return q
def postorderTraveral2(self, root):
"""
迭代法：利用兩個stack來儲存節(jié)點痢畜。
后序遍歷：左/右/根垛膝，反過來是：根/右/左鳍侣， 這跟先序遍歷類似
"""
if root is None:
return []
stack = []
output = []
cur = root
while stack or cur:
if cur:
output.append(cur.var)
stack.append(cur.left)
cur = cur.right
else:
stack.pop()
return output[::-1]
二丁稀、廣度遍歷
class Solution(object):
def breadthTraveral(self, root):
"""
迭代法
利用隊列實現(xiàn)二叉樹的層次遍歷
"""
if root is None:
return []
q = []
output = []
q.append(root)
while q:
cur = q.pop(0)
output.append(cur.var)
if cur.left != None:
q.append(cur.left)
if cur.right != None:
q.append(cur.right)
return output
三、二叉樹遍歷進(jìn)階
Leetcode105. 從前序與中序遍歷序列構(gòu)造二叉樹
思路：
- 采用遞歸方法
- 終止條件：子節(jié)點的左右節(jié)點為空倚聚，即preorder 或 inorder的長度為0
- 利用preorder找根節(jié)點
- 找到根節(jié)點之后线衫，在inorder中對根節(jié)點定位，從而分離出左右子樹
- 不斷遞歸惑折，最后遍歷出二叉樹
代碼：
class TreeNode:
def __init__(self, x):
self.val = x
self.right = None
self.left = None
class Solution:
def buildTree(self, preorder, inorder):
if len(preorder) == None:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
return root
Leetcode106. 從中序與后序遍歷序列構(gòu)造二叉樹
思路：
- 與105類似授账，只不過把preorder換成postorder， 利用postorder 來找根節(jié)點, 即index[-1]是二叉樹的根節(jié)點
class TreeNode:
def __init__(self, x):
self.val = x
self.right = None
self.left = None
class Solution:
def buildTree(self, inorder, postorder):
if len(inorder) == 0:
return None
root = TreeNode(postorder[-1]) #構(gòu)造根節(jié)點
mid = inorder.index(postorder[-1])
root.left = self.buildTree(inorder[:mid], postorder[:mid])
root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1])
return root
