定義二叉樹：
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
構(gòu)建二叉樹：
# 返回構(gòu)造的TreeNode根節(jié)點(diǎn)
def reConstructBinaryTree(self, pre, tin):
if not pre or not tin:
return None
root = TreeNode(pre[0])#根節(jié)點(diǎn)
# 判斷輸入的兩個(gè)序列是不是匹配
if set(pre) != set(tin):
return None
i = tin.index(root.val) # i == 3
root.left = self.reConstructBinaryTree(pre[1:i+1],tin[:i]) # 列表：左閉右開
root.right = self.reConstructBinaryTree(pre[i+1:],tin[i+1:])
return root
BFS：
def BFS(self, root): # 寬度優(yōu)先遍歷BFS
array = []
result = []
if root == None:
return result
array.append(root)
while array:
newNode = array.pop(0) # 根結(jié)點(diǎn)
result.append(newNode.val)
if newNode.left != None:
array.append(newNode.left)
if newNode.right != None:
array.append(newNode.right)
return result
先序遍歷：
1.遞歸版本：
def pre_traversal(self):
ret = []
def traversal(head):
if not head:
return
ret.append(head.val)
traversal(head.left)
traversal(head.right)
traversal(self.root)
return ret
2.非遞歸版本:
# 先序打印二叉樹（非遞歸）
def preOrderTravese(node):
stack = [node]
while len(stack) > 0:
print(node.val)
if node.right is not None:
stack.append(node.right)
if node.left is not None:
stack.append(node.left)
node = stack.pop()
中序遍歷：
1.遞歸版本
def in_traversal(self):
ret = []
def traversal(head):
if not head:
return
traversal(head.left)
ret.append(head.val)
traversal(head.right)
traversal(self.root)
return ret
2.非遞歸版本
# 中序打印二叉樹（非遞歸）
def inOrderTraverse(node):
stack = []
pos = node
while pos is not None or len(stack) > 0:
if pos is not None:
stack.append(pos)
pos = pos.left
else:
pos = stack.pop()
print(pos.val)
pos = pos.right
后序遍歷：
1.遞歸版本
def post_traversal(self):
ret = []
def traversal(head):
if not head:
return
traversal(head.left)
traversal(head.right)
ret.append(head.val)
traversal(self.root)
return ret
2.非遞歸版本
# 后序打印二叉樹（非遞歸）
# 使用兩個(gè)棧結(jié)構(gòu)
# 第一個(gè)棧進(jìn)棧順序：左節(jié)點(diǎn)->右節(jié)點(diǎn)->跟節(jié)點(diǎn)(?應(yīng)該是根-左-右？根結(jié)點(diǎn)先進(jìn)棧再出棧，然后左右子節(jié)點(diǎn)入棧休讳？）
# 第一個(gè)棧彈出順序： 跟節(jié)點(diǎn)->右節(jié)點(diǎn)->左節(jié)點(diǎn)(先序遍歷棧彈出順序：跟->左->右)
# 第二個(gè)棧存儲(chǔ)為第一個(gè)棧的每個(gè)彈出依次進(jìn)棧
# 最后第二個(gè)棧依次出棧
def postOrderTraverse(node):
stack = [node]
stack2 = []
while len(stack) > 0:
node = stack.pop()
stack2.append(node)
if node.left is not None:
stack.append(node.left)
if node.right is not None:
stack.append(node.right)
while len(stack2) > 0:
print(stack2.pop().val)
求二叉樹最大深度：
# 二叉樹的最大深度
def bTreeDepth(node):
if node is None:
return 0
print '當(dāng)前節(jié)點(diǎn)',node.data
ldepth = bTreeDepth(node.left)
print ' 節(jié)點(diǎn)', node.data,'的左側(cè)深度',ldepth
rdepth = bTreeDepth(node.right)
print ' 節(jié)點(diǎn)', node.data,'的右側(cè)深度',rdepth
return max(ldepth, rdepth) + 1
求二叉樹節(jié)點(diǎn)個(gè)數(shù)：
# 求二叉樹節(jié)點(diǎn)個(gè)數(shù)
def treeNodenums(node):
if node is None:
return 0
print "當(dāng)前節(jié)點(diǎn)",node.data
nums = treeNodenums(node.left)
print ' ', node.data, '的左節(jié)點(diǎn)數(shù)', nums
right = treeNodenums(node.right)
print ' ', node.data, '的右節(jié)點(diǎn)數(shù)', right
nums = nums + right
print ' ', node.data, '的左右節(jié)點(diǎn)總數(shù)', nums
return nums + 1 # 返回上一級(jí)加上父節(jié)點(diǎn)
