前言
刚开始写算法题时，看到树的题就要烦死了，现在比以前好了点，但也总是忘记思路（毕竟日常真的很少用到这些），开一个坑记录一下树相关的题解吧~
树的层序遍历
从最基本的二叉树开始，树的层序遍历通常来说就是按照树的层数，从上往下的将每一层，按每一层从左到右的顺序遍历出来：
像这样的二叉树，通过层序遍历遍历出来的结果应该是[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作为判断是否执行反转列表的操作，可以很轻松的打印出之字形树
