力扣---广度优先遍历(python实现)

红太狼 2022-11-06 06:53 122阅读 0赞

### 目录 ###

*   *   *  一：从上到下打印二叉树：
         *  二：二叉树的层序遍历（自底向上）:
         *  三： 填充每个节点的下一个右侧节点指针
         *  四：N叉树的层序遍历：
         *  五：二叉树的右视图：

### 一：从上到下打印二叉树： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]

解析： BFS的特点：  
1：首先BFS必须与队列配合使用。  
2：首先初始化队列: 构建一个队列， 然后将根节点加入到队列中。  
3：外层循环控制队列中是否还有元素，有则继续执行。  
4：内层循环可以根据当前队列的长度，判断这一层有多少节点，然后循环遍历，将节点的值加入数组，然后如果当前根节点还有左子树节点则加入到队列中，有右子树也加入到队列中来。

class Solution:
    
        def bfs(self, root):
            res = [] # 构造返回数组
            queue = [] # 构造一个队列
            queue.append(root)# 首先将根节点加入队列
            while(queue):# 一直循环
                temp = []
                for i in range(len(queue)):# 遍历队列
                    node = queue.pop(0) # 弹出这层的元素
                    temp.append(node.val)# 将这层的加入到temp数组中
                    if node.left:
                        queue.append(node.left) # 给队列增加值（下一层的节点）
                    if node.right:
                        queue.append(node.right)
                res.append(temp) # 将temp数组加入结果数组
            return res
    
    
        def levelOrder(self, root: TreeNode) -> List[List[int]]:
            if root == None:
                return []
            else:
                return self.bfs(root)

### 二：二叉树的层序遍历（自底向上）: ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]

class Solution:
    
        def bfs(self, root):
            res = [] # 构造返回数组
            queue = [] # 构造一个队列
            queue.append(root)# 首先将根节点加入队列
            while(queue):# 一直循环
                temp = []
                for i in range(len(queue)):# 遍历队列
                    node = queue.pop(0) # 弹出这层的元素
                    temp.append(node.val)# 将这层的加入到temp数组中
                    if node.left:
                        queue.append(node.left) # 给队列增加值（下一层的节点）
                    if node.right:
                        queue.append(node.right)
                res.append(temp) # 将temp数组加入结果数组
            return res[::-1]
    
    
        def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
            if root == None:
                return []
            else:
                return self.bfs(root)

### 三： 填充每个节点的下一个右侧节点指针 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]

分析： 层序遍历，中间让每个节点指向下一个节点。

class Solution:
    
    
        def bfs(self, root):
            queue = [] # 初始化队列
            queue.append(root) # 节点加入队列
            while(queue):
                length = len(queue)
                for i in range(length):
                    node = queue.pop(0)# 取出这一层的元素（循环取）
                    if i < length - 1: # 如果不是这一行最后一个元素，则指针指向右测
                        node.next = queue[0]
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
            return root
    
        def connect(self, root: 'Node') -> 'Node':
            if root == None:
                return root
            else:
                return self.bfs(root)

### 四：N叉树的层序遍历： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]  
原理还是层序遍历，只不过加入的时候，采用循环加入节点。

class Solution:
    
        def bfs(self, root):
            res = []
            queue = []
            queue.append(root)
    
            while queue:
                level = []
                for i in range(len(queue)):
                    node = queue.pop(0)
                    level.append(node.val)
                    for j in node.children:
                        queue.append(j)
                res.append(level)
            return res
    
    
        def levelOrder(self, root: 'Node') -> List[List[int]]:
            if root is None:
                return []
            else:
                return self.bfs(root)

### 五：二叉树的右视图： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]  
层序遍历，如果是最后一层，则加入列表。

class Solution:
    
        def bfs(self, root):
            queue = []
            res = []
            queue.append(root)
            while(queue):
                length = len(queue)
                for i in range(length):
                    node = queue.pop(0)
                    if i == length -1:
                        res.append(node.val)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
            return res
                
    
        def rightSideView(self, root: TreeNode) -> List[int]:
            if root is None:
                return []
            else:
                return self.bfs(root)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70]: /images/20221023/430c7c3485b947c9a84905e7704ba8da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 1]: /images/20221023/eaeacf535526401183e4b4cf34d686be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 2]: /images/20221023/dd700d44f6d04aa58d958c308a80ac6f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 3]: /images/20221023/cf7508f3d0f04848ab25c7a0d04fdf43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzQxNzU3_size_16_color_FFFFFF_t_70 4]: /images/20221023/3b276662e13c4928a6ab2918b2e0eddc.png