每日一道 LeetCode (23)：二叉树的层次遍历 II
共 2481字，需浏览 5分钟
·
2020-08-20 11:15
❝每天 3 分钟，走上算法的逆袭之路。
❞
前文合集
代码仓库
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
题目：二叉树的层次遍历 II
题目来源：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
给定一个二叉树，返回其节点值自底向上的层次遍历。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
例如：给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为：
[
[15,7],
[9,20],
[3]
]
解题思路
看到这道题，如果还有不会做的同学，可能需要受到马桶搋子的教育。
这道题和昨天的那道题基本上是同一道题，昨天的那道题是一个顺序遍历，这道题是一个逆序遍历。
顺序遍历使用的是队列的结构，逆序遍历能想到啥？
当然是栈啊，队列是先进先出的数据结构，而栈是一个先进后出的数据结构。
在使用栈的时候只要按照循序把元素一个一个放进去放好，最后再拿出来直接就是一个逆序的结构，完全不需要多余的处理的好么。
解法一：使用栈
这个解法就是把昨天的代码上加上一个栈，在每次循环的时候把元素放到栈里，最后迭代一次栈，将栈中的元素输出后返回。
// 顺序思维操作 耗时 2ms
public List> levelOrderBottom(TreeNode root) {
if (root == null) return new ArrayList<>();
List> result = new ArrayList<>();
Queue queue = new LinkedList<>();
queue.offer(root);
// 新增一个数据结构，栈
Stack> stack = new Stack<>();
// 外层循环，每次循环都是一层
while (!queue.isEmpty()) {
int size = queue.size();
List list = new ArrayList<>();
// 循环这一层的所有节点
while (size > 0) {
TreeNode node = queue.poll();
// 将这一层的所有节点放到 list 中
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
size--;
}
// 将列表当道栈中
stack.push(list);
}
// 将栈中数据取出来放到列表中
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
这段代码稍微有点长，不过很好理解，完全的顺序思维。
不知道你们发现没有，越长的代码越容易看懂，越短的代码理解起来越费劲，就比如昨天的那个递归的方法，总共就两行，想看懂还是有点难度的。
解法二：使用 List 代替栈
上面的解法耗时稍微有点长，我们需要先把数据赛到栈里，然后再迭代整个栈把元素逆序输出，那么能不能优化一下呢？
当然可以，我们可以不适用栈，直接使用列表的 List.add(int index,E element) 这个方法，这个方法不懂的建议直接度娘。
// 优化代码，不适用栈，直接使用 list.add 方法，耗时 1ms
public List> levelOrderBottom_1(TreeNode root) {
List> result = new LinkedList<>();
if (root == null) return result;
Queue queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List list = new ArrayList<>();
while (size > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
size--;
}
result.add(0, list);
}
return result;
}
这段代码没有加注释，和上面那段基本一样，只是单纯的去掉了栈，在循环中使用 result.add(0, list); 将元素放入列表中，从而实现逆序列表的输出。
