二叉树的层序遍历

雨点打透心脏的1/2处 2023-10-14 17:53 48阅读 0赞

**目录**

题目

示例

示例1

示例2

示例3

解题

1.对层序遍历的理解

画图理解

2.解题思路

1.选择数据结构队列来非递归实现

队列的简单介绍

2.视频动态演示解题思路

3.文字解释解题思路

3.对上述思路实现的代码(但不符合题意!ε=(´ο｀\*)))唉)

4.代码运行结果

5.问题所在

6.对上述代码进行改进

改进的代码

注:阿里面试题:输出一颗二叉树的左视图,其实就是这道层序遍历题的变种题,建议掌握哟!ヾ(◍°∇°◍)ﾉﾞ

完结撒花✿✿ヽ(°▽°)ノ✿✿

--------------------

## 题目 ##

**给你二叉树的根节点 `root` ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）**

题目链接:[https://leetcode.cn/problems/binary-tree-level-order-traversal/][https_leetcode.cn_problems_binary-tree-level-order-traversal]

--------------------

## 示例 ##

### 示例1 ###

![d024f853e8c94127b6679a123bb3e62f.jpeg][]

> **输入：root = \[3,9,20,null,null,15,7\]** 
> 
> **输出：\[\[3\],\[9,20\],\[15,7\]\]**

### 示例2 ###

> **输入：root = \[1\]**
> 
> **输出：\[\[1\]\]**

### 示例3 ###

> **输入：root = \[\]** 
> 
> **输出：\[\]**

**提示**

*  **树中节点数目在范围 `[0, 2000]` 内**
 *  **`-1000 <= Node.val <= 1000`**

--------------------

## 解题 ##

### 1.对层序遍历的理解 ###

> **自上而下，自左至右逐层访问树的结点的过程就是层序遍历**
> 
> **设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推**

#### 画图理解 ####

![40dbd2dc97de49d88e340928b380998a.png][]

### 2.解题思路 ###

#### 1.选择**数据结构队列**来非递归实现 ####

##### 队列的简单介绍 #####

> **队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out)** 
> 
> **入队列：进行插入操作的一端称为队尾（Tail/Rear）** 
> 
> **出队列：进行删除操作的一端称为队位（Head/Front)**

![87c73851eecf40f78b81a822e3863e04.png][]

#### 2.视频动态演示解题思路 ####

动态演示用队列实现层序遍历的过程

#### 3.文字解释解题思路 ####

1.定义一个cur,让cur=root,当cur不为null时,把A放入队列中,因为队列不为空,弹出A的同时打印A;

2.A的左边不为空,把A的左边放入栈中,A的右边不为空,把A的右边放入栈中;

3.现在栈不为空了,弹出队头B的同时打印B,再让cur=B;

4.B的左边不为空,把B的左边放入栈中,B的右边不为空,把B的右边放入栈中;

5.现在栈不为空了,弹出队头C的同时打印C,再让cur=C;

6.C的左边不为空,把C的左边放入栈中,C的右边不为空,把C的右边放入栈中;

7.再弹出队头元素D的同时打印D,再让cur=D,因为D的左右同时都为空,左右不放入队列;

8.当前队列不为空,再弹出队头元素E的同时打印E,再让cur=E,因为E的左右同时都为空,左右不放入队列;

9.当前队列不为空,再弹出队头元素E的同时打印F,再让cur=E,因为F的左右同时都为空,左右不放入队列;

10.当前队列不为空,再弹出队头元素E的同时打印G,再让cur=G因为G的左右同时都为空,左右不放入队列;

11.当前队列为空,程序结束.

**注:入栈的时候一定要先入左再入右,才能保证从左到右的打印**

--------------------

### 3.对上述思路实现的代码(但不符合题意!ε=(´ο｀\*)))唉) ###

public class Solution {
        public void levelOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                System.out.println(cur.val + " ");
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    }

### 4.代码运行结果 ###

![5cf707987d7949dc86a0d8c9e13bfd01.png][]

### 5.问题所在 ###

> **class Solution \{** 
> 
>  **public List<List<Integer>> levelOrder(TreeNode root) \{** 
> 
>  **\}**
> 
> **\}**

**1.题目所给的方法具有返回值List<List<Integer>>**

**2.结合示例的输出可知我们得确定所给二叉树的每一层有哪些节点**

--------------------

### 6.对上述代码进行改进 ###

![8284ed1461244167908df2ab7c80890b.png][]

#### 改进的代码 ####

public class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list = new ArrayList<>();
            if (root == null) {
                return list;//根节点为null,返回一个空的list
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();//每次循环,求出当前元素的个数,也就是二叉树在当前这一层的节点个数
                List<Integer> tmp = new ArrayList<>();//每次循环创建链表tmp,为了来存储当前这一层的节点
    
                while (size!=0) {//通过循环添加当前这层的所有节点到链表tmp中
                    TreeNode cur = queue.poll();
                    tmp.add(cur.val);//添加当前节点到链表tmp中
                    if (cur.left != null) {
                        queue.offer(cur.left);
                    }
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                }
                list.add(tmp);//将小的链表tmp添加到大的链表list,来作为方法的返回值
            }
            return list;
            //时间复杂度为O(n)
        }
    }

**运行结果**

![2d606a7e7bad4b72819b062ea6912837.png][]

## 注:阿里面试题:输出一颗二叉树的左视图,其实就是这道层序遍历题的变种题,建议掌握哟!ヾ(◍°∇°◍)ﾉﾞ ##

## 完结撒花✿✿ヽ(°▽°)ノ✿ ##

![d93d5f8e84074bff81b9da78ec9ca027.gif][]

[https_leetcode.cn_problems_binary-tree-level-order-traversal]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[d024f853e8c94127b6679a123bb3e62f.jpeg]: https://img-blog.csdnimg.cn/d024f853e8c94127b6679a123bb3e62f.jpeg
[40dbd2dc97de49d88e340928b380998a.png]: https://img-blog.csdnimg.cn/40dbd2dc97de49d88e340928b380998a.png
[87c73851eecf40f78b81a822e3863e04.png]: https://img-blog.csdnimg.cn/87c73851eecf40f78b81a822e3863e04.png
[5cf707987d7949dc86a0d8c9e13bfd01.png]: https://img-blog.csdnimg.cn/5cf707987d7949dc86a0d8c9e13bfd01.png
[8284ed1461244167908df2ab7c80890b.png]: https://img-blog.csdnimg.cn/8284ed1461244167908df2ab7c80890b.png
[2d606a7e7bad4b72819b062ea6912837.png]: https://img-blog.csdnimg.cn/2d606a7e7bad4b72819b062ea6912837.png
[d93d5f8e84074bff81b9da78ec9ca027.gif]: https://img-blog.csdnimg.cn/d93d5f8e84074bff81b9da78ec9ca027.gif