二叉树广度和深度遍历的全部算法

二叉树广度和深度遍历的全部算法

对于二叉树的遍历，有广度遍历和深度遍历两大类，对于深度遍历又分为先序、中序和后序，这三种先中后序又可以用递归和非递归两种算法来写，下面就分别对这两大类算法做个总结，以后遇到此种问题可以用下面模板来写。

二叉树广度优先遍历

广度优先遍历又叫层次遍历，即对二叉树从上到下，从左到右，一层一层的来遍历。
算法大致流程如下：

• 建立一个空队列用来存放要遍历的节点，初始时先把函数的参数(一般为根节点)加入队列中
• 当队列不为空时，进入循环
  1. 取出队列头部节点，并对所取节点进行相关处理操作
  2. 判断如果节点左子节点不为空，则将左子节点加入队列
  3. 判断如果节点右子节点不为空，则将右子节点加入队列
• 退出循环，若需要返回参数则返回参数
  注意：若需要利用层数，则在进入循环时先求队列长度(每层的节点数)，然后将上面循环内的操作放入一个for 循环中执行，for循环用每层节点数来控制
  举个🌰 ：104.二叉树的最大深度
  在此题中，求二叉树的深度，即为求二叉树的层数，我们可以用广度遍历算法来求，每到一层，就将深度加1，流程在上面我已经说明，接下来看代码，以后遇到此种类型题，都可以将下面代码作为模板。

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        """广度优先遍历"""
        if root is None:
        	return 0
        depth = 0
        queue = collections.deque()  # 创建空队列存放要遍历的节点
        queue.append(root)  # 初始将函数的参数(一般为根节点)加入队列
        # 当队列不为空时进入循环
        while queue:
        	# 求每层的节点数
        	size = len(queue)
        	# 每到一层，深度加1
        	depth  = 1
        	# 用每层的节点数控制一个for循环
        	for i in range(size):
        		# 取出队列头部节点
        		node = queue.pop()  
        		# 判断节点左子节点
        		if node.left:
        			queue.append(node.left)
        		# 判断节点右子节点
        		if node.right:
        			queue.append(node.right)
        return depth
        

二叉树深度优先遍历

二叉树的深度优先遍历包括三种：先序(根左右)、中序(左根右)、后序(左右根)。对于先序则先处理根节点，再到根节点的左子树，然后再右子树，到左子树同样看成一颗二叉树，依然按照根左右来处理。对于中序则先看根节点的左子树，同样左子树也看成一颗二叉树，按照左根右来处理，同理，后序先是左子树再右子树，最后到根。
下面以后序遍历为例，由图(a)~(f)展示了后序遍历过程，先看根节点3的左子树为单节点9，则直接输出9；然后看其右子树，当成一个整体来看，右子树为以2为根节点的二叉树，则先看其左子树，左子树为单节点1，则输出1，然后再到右边为单节点7，则输出7，最后到根节点2，到此，以3为根节点的右子树遍历完成；最后再到根节点3，输出3。

对于先中后序有递归和非递归两种算法，下面分别作以介绍。

递归深度优先遍历

深度优先遍历用递归来写就比较简单了，一般递归主要有三步：

1. 递归终止条件
2. 递归的参数和返回值
3. 单层递归逻辑

对于先中后序，显然递归终止条件为当所遇到的节点为空时终止；整个函数的参数为传入的二叉树的某个节点（一般为根节点）而递归的参数则为这个根节点的左(右)子节点；至于递归的逻辑和所遍历的顺序有关。
算法大致流程如下：

• 如果节点node为空，则返回退出（递归终止条件）
• 递归调用自身，传入参数为node.left（左）
• 递归调用自身，传入参数为node.right（右）
• 处理根节点（根）
  以上为后序的算法大致流程，若为先序则先处理根节点，再递归调用左右节点，若为中序，则先递归左节点，再处理根节点，再递归右节点，实际上就是改变了上面的执行顺序而已。

代码

class Solution(object):
	def preorder(self, node):
		"""递归深度优先遍历（先序 根左右）"""
		if node is None:
			return
		print(node.item, end = '')  # 处理根节点
		self.preorder(node.left)  # 递归左节点
		self.preorder(node.right)  # 递归右节点
		
	def inorder(self, node):
		"""递归深度优先遍历（中序 左根右）"""
		if node is None:
			return
		self.preorder(node.left)  # 递归左节点
		print(node.item, end = '')  # 处理根节点
		self.preorder(node.right)  # 递归右节点
		
	def postorder(self, node):
		"""递归深度优先遍历（后序 左右根）"""
		if node is None:
			return
		self.preorder(node.left)  # 递归左节点
		self.preorder(node.right)  # 递归右节点
		print(node.item, end = '')  # 处理根节点	
		

非递归深度优先遍历

深度优先遍历如何用非递归方式来实现呢？在递归时，每次递归的中间结果在计算机内部实际是用一个栈来保存的，那么我们也可以用栈做辅助结构来保存这个数据，代替递归。
在很多非递归深度遍历的写法中，先中后序三种方式没有什么联系，写出其中一种另外两种还是不好写出来，不像递归深度遍历，只要写出其中一种，另外两种改变一下代码顺序就可以了。为了解决这个问题，在这里，我们来写一种统一的写法，前中后序统一个一个地下，便于大家理解记忆。关键就是：将访问的节点存入栈中，将要处理的节点（根节点）也存入栈中，但是紧接着要放一个空指针作为标记；在弹出栈中元素时，所弹元素不为空，则入栈，只有当所弹元素为空时，才将下一个元素作为结果输出。
后序算法大致流程如下：

• 初始新建一个列表用来存放遍历的输出结果，新建一个空栈用来存放节点，并将开始的参数节点(不为空时)加入栈中
• 当栈不为空时，进入循环
  1. 取出栈顶节点
  2. 判断如果节点不为空
     2.1.将节点加入栈，再将一个空指针加入栈（根）
     2.2.如果节点的右子节点不为空，则将右子节点加入栈（右）
     2.3.如果节点的左子节点不为空，则将左子节点加入栈（左）
  3. 否则节点为空，则取出栈顶元素，将所取元素存入结果列表
• 退出循环，返回结果列表
  注意上面算法中的入栈顺序，后序（左右根），则入栈顺序相反，为根右左，因为栈的后进先出的特点，故要反着入栈。而先序和中序，只要改变上面的入栈顺序即可。

代码

class Solution(object):
	def preorder(self, root)
		"""非递归深度优先遍历（先序 根左右）"""
		result = []
		stack = []
		if root:
			stack.append(root)
		while stack:
			node = stack.pop()
			if node:
				if node.right:
					stack.append(node.right)  # 右
				if node.left:
					stack.append(node.left)  # 左
				stack.append(node)  # 根
				stack.append(None)  # 根之后要加入一个空指针
			else:
				r = stack.pop()
				result.append(r.item)
		return result
		
	def inorder(self, root)
		"""非递归深度优先遍历（中序 左根右）"""
		result = []
		stack = []
		if root:
			stack.append(root)
		while stack:
			node = stack.pop()
			if node:
				if node.right:
					stack.append(node.right)  # 右
				stack.append(node)  # 根
				stack.append(None)
				if node.left:
					stack.append(node.left)  # 左
			else:
				r = stack.pop()
				result.append(r.item)
		return result
		
	def postorder(self, root):
		"""非递归深度优先遍历（后序 左右根）"""
		result = []
		stack = []
		if root:
			stack.append(root)
		while stack:
			node = stack.pop()
			if node:
				stack.append(node)  # 根
				stack.append(None)
				if node.right:
					stack.append(node.right) # 右
				if node.left:
					stack.append(node.left)  # 左
			else:
				r = stack.pop()
				result.append(r)
		return result
		

总结：我们来总结一下非递归的深度优先遍历，无非就是用栈来保存访问的节点和要处理的节点（根节点），当栈不为空时进入循环，取出栈顶元素进行判断，元素不为空时就入栈（入栈按照先中后序的相反顺序入栈，如先序为根左右，则入栈就是右左根，并且在根节点后还要再加入一个空指针作为标记），元素为空时，就取出下一个元素出栈作为输出结果。

这篇好文章是转载于：学新通技术网