树遍历（BFS+DFS（递归+非递归））-python代码整理

Love The Way You Lie 2023-01-02 07:25 88阅读 0赞

# 数据结构算法-树 #

最近在刷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