二叉樹的定義，來自leetcode，下面都用python來實(shí)現(xiàn)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
二叉樹的層次遍歷，有BFS和DFS兩種
leetcode 102,103,107
BFS與圖的廣度優(yōu)先遍歷一致，使用隊(duì)列
class Solution(object):
# bfs iterative
def levelOrder(self,root):
if not root:
return []
quene = []
quene.append(root)
res = []
depth = 0
while quene:
index = quene.pop(0)
res.append(index.val)
if index.left:
quene.append(index.left)
if index.right:
quene.append(index.right)
return res
DFS遍歷基于先序遍歷（其他兩種也可以），因?yàn)槎伎梢员ＷC左節(jié)點(diǎn)在右節(jié)點(diǎn)前面進(jìn)入結(jié)果列表
# dfs Recusive
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if not root:
return []
res = [[]]
self.preorder(root,res,0)
return res
def preorder(self,r,res,depth):
if depth > len(res)-1:
res.append([])
res[depth].append(r.val)
if r.left:
self.preorder(r.left,res,depth+1)
if r.right:
self.preorder(r.right,res,depth+1)
擴(kuò)展：判斷一棵樹是否是完全二叉樹
完全二叉樹即一個(gè)數(shù)除了最后一層之上的層都是滿節(jié)點(diǎn)的，最后一層左邊是滿的
如
1
2 3
4 5 7 8
9 10 11 None None None None None
則將每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)如果為NULL都補(bǔ)成一個(gè)特殊元素如#，在層次遍歷輸出，則如果是完全二叉樹這個(gè)特殊元素都在輸出列表的最后
二叉樹的先序，中序，后序遍歷（非遞歸）
遞歸的忽略不講，非遞歸的實(shí)現(xiàn)：先序和中序都基于棧（因?yàn)槭腔赽acktracking回溯的思想）
# 先序，相當(dāng)于用棧一直入左子節(jié)點(diǎn)，同時(shí)打印每個(gè)根節(jié)點(diǎn)的值，遇到左邊為空時(shí)候回溯，此時(shí)添加右子節(jié)點(diǎn)
def pre_order_by_stack(self,r):
if not r:
return
myStack = []
node = r
while node or myStack:
while node:
print(node.root)
myStack.append(node)
node = node.left
node = myStack.pop()
node = node.right
# 中序，與先序基本同理，回溯時(shí)再打印節(jié)點(diǎn)，這樣保證順序是左根右
def in_order_by_stack(self,r):
if not r:
return
myStack = []
node = r
while node or myStack:
while node:
myStack.append(node)
node = node.left
node = myStack.pop()
print(node.root)
node = node.right
后序：先打印出棧節(jié)點(diǎn)，再添加左右子節(jié)點(diǎn)，最后將打印結(jié)果倒轉(zhuǎn)，較難理解，可以背答案。
def post_order(self,r):
if not r:
return
myStack = []
res = []
node = r
myStack.append(node)
while myStack:
node = myStack.pop()
res.append(node.root)
if node.left is not None:
myStack.append(node.left)
if node.right is not None:
myStack.append(node.right)
res.reverse()
return res
二叉查找樹
重建二叉樹
- Construct Binary Tree from Preorder and Inorder Traversal
先序+中序遍歷結(jié)果重建二叉樹，二叉樹沒有重復(fù)元素
先序遍歷的第一個(gè)節(jié)點(diǎn)肯定是根節(jié)點(diǎn)
然后查找這個(gè)節(jié)點(diǎn)的值在中序遍歷結(jié)果的位置，左邊的所有元素在根節(jié)點(diǎn)的左子樹下
右邊的所有元素在根節(jié)點(diǎn)的右子樹下
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder,inorder[0:ind])
root.right = self.buildTree(preorder,inorder[ind+1:])
return root
- Construct Binary Tree from Inorder and Postorder Traversal
中序和后序結(jié)果重建二叉樹
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if postorder:
ind = inorder.index(postorder.pop())
root = TreeNode(inorder[ind])
root.left = self.buildTree(inorder[:ind],postorder[:ind])#[:ind])
root.right = self.buildTree(inorder[ind+1:],postorder[ind:])#[ind+1:])
return root
