数据结构算法-树

最近在刷leetcode的树，整理了常用遍历代码

包含树的层次遍历（

广度优先遍历

）-两种方法

• BFS通用模板 ★★★★★
• 标记法★★★★

前中后序遍历（

深度优先遍历

）-六种方法

1. 暴力递归 ★★★
2. DFS
   
   通用
   
   递归（非暴力递归） ★★★★
3. 非递归迭代栈（前+后），类似层次遍历实现★★★
4. 非递归通用迭代栈（前+
   
   中
   
   +后）★★★★★
5. 标记法迭代栈（前中后）★★★★★
6. 莫里斯遍历

以及N叉树的遍历-（递归与迭代方法）

以及由

前序+中序

确定二叉树 and

中序+后序

确定二叉树

####################

####################

层次遍历（广度优先遍历）★★★★★

1.BFS通用模板

#BFS通用模板，层次遍历通用：
#使用队列实现
def levelOrder(root):
	if not root:
		return []
	queue=[root]
	ans=[]
	while queue:
		a=[]     #方便保存每一层的数据
		for j in range(len(queue)):  #将每一层分割开
			cur=queue.pop(0)
			if not cur:
				return 
			a.append(cur.val)
			if cur.left:
				queue.append(cur.left)
			if cur.right:
				queue.append(cur.right)
		ans.append(a)
	return ans	

2.标记法

#**标记法**：队列实现
#0代表当前未访问，1代表当前已访问
def levelOrder(root):
	ans=[]
	queue=[(0,root)]
	while queue:
		flag,cur= queue.pop(0)   #先进先出
		if not cur:continue
		if flag == 0:
			queue.append((1,cur))
			queue.append((0,cur.left))
			queue.append((0,cur.right))
		else:
			ans.append(cur.val)
	return ans

#########################################

前中后序遍历（深度优先遍历）

**中序非递归遍历最重要，面试经常被问到~**

1 . 暴力递归：

def preorderTraversal(root):
	if not root:
		return []
	return [root.val]+self.preorderTraversal(root.left)+self.preorderTraversal(root.right)  #前序
	return self.inorderTraversal(root.left)+[root.val]+self.inorderTraversal(root.right)  #中序
	return self.postorderTraversal(root.left)+self.postorderTraversal(root.right)+[root.val]  #后序

2 . DFS通用递归：

def preorderTraversal(root):   #前序
	def DFS(cur):
		if not cur:
			return 
		ans.append(cur.val)
		DFS(cur.left)
		DFS(cur.right)
	ans=[]
	DFS(root)
	return ans

#中序与后序只需要更改DFS函数体内，三行代码的顺序

3 . 非递归迭代栈（前+后）

#非递归迭代，用栈实现，类似层次遍历中的队列实现
#前序：
def preorderTraversal(root):
	if not root:
		return []
	stack=[root]
	ans=[]
	while stack:
		node=stack.pop()
		ans.append(node.val)
		if node.right:         #先右再左，不能反 ，使得出栈时候左先出
			stack.append(node.right)
		if node.left;
			stack.append(node.left)
	return ans

#后序
def postorderTraversal(root):
	if not root:
		return []
	stack=[root]
	ans=[]
	while stack:
		node=stack.pop()
		ans.append(node.val)
		if node.left:             #进：先左再右，出：先右再左
			stack.append(node.left)
		if node.right:
			stack.append(node.right)
	return ans[::-1]

4 . 非递归通用栈（前

中

后）-

中最重要

#前序：★★★★
def preorderTraversal(root):
	if not root:
		return []
	stack=[]
	ans=[]
	cur=root
	while cur or stack:
		while cur:            #找到每颗子树的最左下角
			ans.append(cur.val)
			stack.append(cur)
			cur=cur.left
		cur=stack.pop()
		cur=cur.right
	return ans


#中序：★★★★★
def inorderTraversal(root):
	if not root:
		return []
	stack=[]
	ans=[]
	cur=root
	while cur or stack:
		while cur:            #找到每颗子树的最左下角
			stack.append(cur)
			cur=cur.left
		cur=stack.pop()
		ans.append(cur.val)
		cur=cur.right
	return ans

#后序：★★★★
def postorderTraversal(root):
	if not root:
		return []
	stack=[]
	ans=[]
	cur=root
	while cur or stack:
		while cur:
			ans.append(cur.val)
			stack.append(cur)
			cur=cur.right         #相比前序，后序应先找到最右下子树，得到：根-右-左，最后反转
		cur=stack.pop()
		cur=cur.left
	return ans[::-1]

5 . 标记法迭代：

#**标记法**：栈实现
#0代表当前未访问，1代表当前已访问
def inorderTraversal(root):   #中序
	ans=[]
	stack=[(0,root)]
	while stack:
		flag,cur= stack.pop()
		if not cur:continue
		if flag == 0:
			stack.append((0,cur.right))
			stack.append((1,cur))
			stack.append((0,cur.left))
		else:
			ans.append(cur.val)
	return ans

#前序:
		......
		if flag == 0:
			stack.append((0,cur.right))
			stack.append((0,cur.left))
			stack.append((1,cur))
		......

#后序：
		......
		if flag == 0:
			stack.append(1,cur)
			stack.append((0,cur.right))
			stack.append((0,cur.left))
		......

N叉树的遍历（递归+迭代）

#1.递归解法
def preorder(root):
	res=[]
	def DFS(root):
		if not root:return 
		res.append(root.val)
		for child in root.children:
			DFS(child)
	DFS(root)
	return res
#后序只需要调整函数体内部顺序就行

#2.迭代解法
def preorder(root):
	if not root:return[]
	stack=[root]
	res=[]
	while stack:
		cur=stack.pop()
		res.append(cur.val)
		for child in cur.children[::-1]:
			stack.append(child)
	   #stack.extend(cur.children[::-1])
	return res  

def postorder(root):
	if not root:return []
    stack=[root]
    res=[]
    while stack:
        cur=stack.pop()
        res.append(cur.val)
        for child in cur.children:
             stack.append(child)
        #stack.extend(cur.children)
    return res[::-1]        

二叉树的确定（前+中 and 中+后）

前序/后序+中序序列可以唯一确定一棵二叉树，必须包含中序，否则无法确定树的形状

class TreeNode:   #定义树节点
	def __init__(self,val=0,left=None,right=None):
		self.val=val
		self.left=left
		self.right=right
		
#前序+中序
def buildTree(self, preorder: List[int], inorder: List[int]):
	if not preorder:return None
	root=TreeNode(preorder[0])      #前序第一项为根节点
	index=inorder.index(root.val)    #找到中序根节点，其左右两侧即为左子树和右子树
	root.left=self.buildTree(preorder[1:1+index],inorder[:index])
	root.right=self.buildTree(preorder[1+index:],inorder[index+1:])
	return root

#中序+后序
def buildTree(self, inorder: List[int], postorder: List[int]):
	if not postorder:return None
	root=TreeNode(postorder[-1])       #后序最后一项为根节点
	index_1=inorder.index(root.val)    
	root.left=self.buildTree(inorder[:index],postorder[:index])
	root.right=self.buildTree(inorder[index+1:],postorder[index:-1])
	return root