二叉树进阶-学会层序遍历助你一次刷完leetcode10道题

简介: 文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。

前言

算法是计算机软件的基础,常见算法是软件开发的核心基本功,今年打算深入学习一些算法,记录一些算法理论以及最佳实践,希望可以坚持下去,关注我,我们一起学习,增强我们的基本功。

本文内容是层序遍历二叉树,学会了层序遍历的方法,leetcode上的10道题目都可以轻松解决,真的无敌啊。

102. 二叉树的层序遍历

104. 二叉树的最大深度

107. 二叉树的层序遍历 II

111. 二叉树的最小深度

116. 填充每个节点的下一个右侧节点指针

117. 填充每个节点的下一个右侧节点指针 II

199. 二叉树的右视图

429. N 叉树的层序遍历

515. 在每个树行中找最大值

637. 二叉树的层平均值

image.png

一、层序遍历概述

层序遍历是一层一层的遍历二叉树。由于递归遍历是一种深度搜索的方式,因此递归遍历在这里是行不通的。

image.png

10

6 16

1 8 12 19

我们可以发现下一层,在上一层遍历完成之后就可以确定了,因为我们遍历一层的时候,把子节点记录下来就可以。因此我们在遍历当前层的时候可以把下一层的节点存储起来。为了确保是从左到右顺序按层遍历元素,我们使用队列这种数据结构来存储。

比如上图的树

首先我们把根节点加入队列,这时队列里存储了第一层的数据,我们开始遍历队列里的第一层根节点10;遍历同时同时把左右节点6,16存储起来。

遍历完第一层,这时开始遍历第二层,循环队列里面两个元素,我们可以得到第三层的节点并存储到队列中。

二、层序遍历实战

leetcode102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
   
   
    public List<List<Integer>> levelOrder(TreeNode root) {
   
   
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
   
   
            return result;
        }

        List<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
   
   
            //下一层的大小,
           int size =  queue.size();
           List<Integer> raw = new ArrayList<>();
           //遍历某一层
           for(int i=0; i<size; i++) {
   
   
              TreeNode node =  queue.removeFirst();
              raw.add(node.val);
              if(node.left != null) {
   
   
                  queue.add(node.left);
              }

              if(node.right != null) {
   
   
                  queue.add(node.right);
              }
           }
           //记录一层的数据
           result.add(raw);
        }
        return result;
    }
}

三、总结

层序遍历是一种广度优先搜索的遍历方式,掌握一层一层遍历二叉树的方法,真的可以解决文字开头说的10道题。

102. 二叉树的层序遍历

104. 二叉树的最大深度

107. 二叉树的层序遍历 II

111. 二叉树的最小深度

116. 填充每个节点的下一个右侧节点指针

117. 填充每个节点的下一个右侧节点指针 II

199. 二叉树的右视图

429. N 叉树的层序遍历

515. 在每个树行中找最大值

637. 二叉树的层平均值

相关文章
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
47 6
|
2月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
24 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
2月前
|
算法 Java
LeetCode第94题二叉树的中序遍历
文章介绍了LeetCode第94题"二叉树的中序遍历"的解法,使用递归实现了中序遍历的过程,遵循了"左根右"的遍历顺序,并提供了清晰的Java代码实现。
LeetCode第94题二叉树的中序遍历
|
2月前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树,其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
40 7
|
2月前
|
存储 算法 Python
【Leetcode刷题Python】297. 二叉树的序列化与反序列化
LeetCode第297题"二叉树的序列化与反序列化"的Python语言解决方案,包括序列化二叉树为字符串和反序列化字符串为二叉树的算法实现。
22 5
|
2月前
|
Python
【Leetcode刷题Python】236. 二叉树的最近公共祖先
LeetCode上236号问题"二叉树的最近公共祖先"的Python实现,使用递归方法找到两个指定节点的最近公共祖先。
31 5
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - II. 从上到下打印二叉树 II
本文提供了一种Python实现方法,用于层次遍历二叉树并按层打印结果,每层节点按从左到右的顺序排列,每层打印到一行。
31 3
|
2月前
|
Python
【Leetcode刷题Python】199. 二叉树的右视图
LeetCode上199号问题"二叉树的右视图"的Python实现,通过深度优先搜索算法按层序从右向左访问节点,以获取每层的最右边节点的值。
21 4
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - I. 从上到下打印二叉树
本文介绍了使用Python实现从上到下打印二叉树的解决方案,采用层次遍历的方法,利用队列进行节点的访问。
31 2
|
2月前
|
Python
【Leetcode刷题Python】105. 从前序与中序遍历序列构造二叉树
LeetCode上105号问题"从前序与中序遍历序列构造二叉树"的Python实现,通过递归方法根据前序和中序遍历序列重建二叉树。
18 3