二叉树的定义，来自leetcode，下面都用python来实现
# 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与图的广度优先遍历一致，使用队列
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遍历基于先序遍历（其他两种也可以），因为都可以保证左节点在右节点前面进入结果列表
# 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)
扩展：判断一棵树是否是完全二叉树
完全二叉树即一个数除了最后一层之上的层都是满节点的，最后一层左边是满的
如
1
2 3
4 5 7 8
9 10 11 None None None None None
则将每个节点的左右子节点如果为NULL都补成一个特殊元素如#，在层次遍历输出，则如果是完全二叉树这个特殊元素都在输出列表的最后
二叉树的先序，中序，后序遍历（非递归）
递归的忽略不讲，非递归的实现：先序和中序都基于栈（因为是基于backtracking回溯的思想）
# 先序，相当于用栈一直入左子节点，同时打印每个根节点的值，遇到左边为空时候回溯，此时添加右子节点
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
# 中序，与先序基本同理，回溯时再打印节点，这样保证顺序是左根右
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
后序：先打印出栈节点，再添加左右子节点，最后将打印结果倒转，较难理解，可以背答案。
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
先序+中序遍历结果重建二叉树，二叉树没有重复元素
先序遍历的第一个节点肯定是根节点
然后查找这个节点的值在中序遍历结果的位置，左边的所有元素在根节点的左子树下
右边的所有元素在根节点的右子树下
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
中序和后序结果重建二叉树
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
