广度优先遍历BFS思想在二叉树中的应用总结（python详解）

广度优先遍历（Breadth First Search）思想在二叉树中可用来解决多种问题，常见问题以及python代码详解

首先回顾一下树的广度优先遍历，即树的层次遍历

主要思想：使用队结构，先访问根节点，再将对应的左子树、右子树分别入队

def bfs(root): tree_list=[] queue=[root] while queue: node=queue.pop(0) if node: tree_list.append(node.val) queue.append(node.left) queue.append(node.right) return tree_list

1.二叉树的深度

树的深度：从根节点到叶子节点路径中的节点个数

1）二叉树最大深度

主要思想：层序遍历，每遍历一层，深度加一（用队存储每一层的节点） 力扣网址：力扣中对应题目网址

def max_depth(root): if not root: return 0 if not root.left and not root.right: return 1 depth=0 queue=[root] while queue: tmp=[] for node in queue: if node.left:tmp.append(node.left) if node.right:tmp.append(node.right) depth+=1 queue=tmp return depth

2）二叉树最小深度

主要思想：使用队层序遍历将对应的节点和深度入队，找到队中第一个没有左右子树的节点，即二叉树最小深度（不需要访问所有的节点） 力扣中对应题目网址

def min_depth(root): if not root: return 0 queue=[(root,1)] while queue: node,depth=queue.pop(0) if not node.left and not node.right: return depth if node.left:queue.append((node.left,depth+1)) if node.right:queue.append((node.right,depth+1)) return depth

2.二叉树的最大宽度

主要思路：层序遍历，每次将节点和对应下标索引入队，树的宽度=每层的最右边节点索引-最左边节点索引+1 力扣中对应题目网址

def max_width(root): if not root: return 0 queue=[(root,0)] max_width=1 while queue: max_width=max(max_width,queue[-1][1]-queue[0][1]+1) tmp=[] for node,i in queue: if node.left:tmp.append((node.left,2*i+1)) if node.right:tmp.append((node.right,2*i+2)) queue=tmp return max_width

3.翻转二叉树

主要思路：层序遍历思想，节点入队，交换对应节点的左右子树，再将左右子树（存在）分别入队 力扣中对应题目网址

def invert_tree(root): if not root: return root queue=[root] while queue: node=queue.pop(0) node.left,node.right=node.right,node.left if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root

4.对称二叉树:给定二叉树判断是否镜像对称

主要思路：层序遍历，用队存储每一层的节点，判断每一层正反输出是否一样 力扣中对应题目网址

def symmetric_tree(root): if not root: return True queue=[root] while queue: level_node=[] level_list=[] for node in queue: if node: level_list.append(node.val) level_node.append(node.left) level_node.append(node.right) else: level_list.append("null") if level_list!=level_list[::-1]: return False queue=level_node return True