前言
刚开始写算法题时,看到树的题就要烦死了,现在比以前好了点,但也总是忘记思路(毕竟日常真的很少用到这些),开一个坑记录一下树相关的题解吧~
导航
- 前言
- 树的层序遍历
- 题解
-
- 剑指 Offer 32 - II. 从上到下打印二叉树 II
- LeetCode 107. 二叉树的层次遍历 II
- 剑指 Offer 32 - III. 从上到下之字形打印二叉树 III
树的层序遍历
从最基本的二叉树开始,树的层序遍历通常来说就是按照树的层数,从上往下的将每一层,按每一层从左到右的顺序遍历出来:
剑指 Offer 32 - I. 从上到下打印二叉树
像这样的二叉树,通过层序遍历遍历出来的结果应该是[3,9,20,15,17]
在没有任何其它特殊要求的情况下,我们借助队列直接把树层序遍历出来:
import java.util.*;
class Solution {
public int[] levelOrder(TreeNode root) {
List<Integer> res=new ArrayList<>();
// 空值检测
if(root == null){
return new int[0];
}
// 借助队列在存放树节点
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
// 拿出队头进行操作
TreeNode tmp = queue.poll();
// 这里的入队操作是先左后右,保证每层的打印顺序是从左到右
// 当队头的左节点非空,将其左节点入队
if(tmp.left != null){
queue.offer(tmp.left);
}
// 当队头的左节点非空,将其左节点入队
if(tmp.right != null){
queue.offer(tmp.right);
}
// 将当前取出的队头输出(添加到结果列表)
res.add(tmp.val);
}
// 将List转化为int[]
return res.stream().mapToInt(Integer::valueOf).toArray();
}
}
题解
学会了用队列来做层序遍历后,我们会遇到一些题目让你应用层序遍历来解题,如:
剑指 Offer 32 - II. 从上到下打印二叉树 II
力扣链接
和之前简单的打印出一个数组相比,这道题还需要对每一层的节点进行分割,加大了难度
我们可以在之前的基础上改造一下,使层次遍历的每一层都能在我们的掌握之中
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
// 每次进入while循环时,判断【当前队列】长度
int len = queue.size();
// 创建一个ArrayList对象
// 用来添加当前层(即【当前队列】)的节点值
List<Integer> list = new ArrayList<>();
// 遍历【当前队列】
while(len-- > 0){
TreeNode tmp = queue.poll();
if(tmp.left != null){
queue.offer(tmp.left);
}
if(tmp.right != null){
queue.offer(tmp.right);
}
// 将【当前队列】的值都装进list中
list.add(tmp.val);
}
// 将list装入res列表中
res.add(list);
}
return res;
}
为什么队列的长度=每一层的节点个数呢?我们从第一层开始推:
- 当队列中只有根节点时,队列长度为1,通过获取根节点的左右节点,并将根节点出队,我们可以得到下一层的队列中有根节点的左节点和右节点
- 此时队列长度为2,对该队列进行遍历,获取该队列中的节点,并由这些节点获取到这些节点的左/右子节点
- 在以后的外层while循环中,每一次外层while循环获取到的队列长度都是树每一层的节点个数
LeetCode 107. 二叉树的层次遍历 II
力扣链接
这道题就是将剑指 Offer 32 - II. 从上到下打印二叉树 II的输出反过来而已,直接在它的基础上在最后加上Collection.reverse(List list)即可
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int len = queue.size();
while(len-- > 0){
TreeNode tmp=queue.poll();
if(tmp.left != null){
queue.offer(tmp.left);
}
if(tmp.right != null){
queue.offer(tmp.right);
}
list.add(tmp.val);
}
res.add(list);
}
// 遍历完反转一下
Collections.reverse(res);
return res;
}
剑指 Offer 32 - III. 从上到下之字形打印二叉树 III
力扣链接
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
之字形打印的话,最简单的方式,在剑指 Offer 32 - II. 从上到下打印二叉树 II的基础上,只需要活用Collections.reverse(List list)这个方法即可
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null){
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 定义变量reverse,由于是偶数行需要反转,所以初值为false
boolean reverse = false;
while(!queue.isEmpty()){
int len = queue.size();
List<Integer> list = new ArrayList<>();
while(len-- > 0){
TreeNode tmp = queue.poll();
if(tmp.left != null){
queue.offer(tmp.left);
}
if(tmp.right != null){
queue.offer(tmp.right);
}
list.add(tmp.val);
}
// 当reverse为true时,将list反转
if(reverse){
Collections.reverse(list);
}
// 将reverse取反
reverse =! reverse;
res.add(list);
}
return res;
}
通过定义一个布尔类型的变量reverse作为判断是否执行反转列表的操作,可以很轻松的打印出之字形树