开启掘金成长之旅！这是我参与「掘金日新计划 · 12 月更文挑战」的第2天，点击查看活动详情
LeetCode 第107题
题目描述（中等难度）
树的层次遍历，和 102 题 的不同之处是，之前输出的数组顺序是从根部一层一层的输出，现在是从底部，一层一层的输出。
解法一 DFS
把 102 题的DFS贴过来看一下。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
DFS(root, 0, ans);
return ans;
}
private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
if(root == null){
return;
}
//当前层数还没有元素，先 new 一个空的列表
if(ans.size()<=level){
ans.add(new ArrayList<>());
}
//当前值加入
ans.get(level).add(root.val);
DFS(root.left,level+1,ans);
DFS(root.right,level+1,ans);
}
Copy
之前我们根据 level 得到数组的位置，然后添加。
ans.get(level).add(root.val);
ans [] [] [] [] [].
index 0 1 2 3 4
level 0 1 2 3 4
------------>
index = 0 + level
现在 level 是逆过来存的
ans [] [] [] [] [].
index 0 1 2 3 4
level 4 3 2 1 0
<------------
index = 4 - level
4 就是 ans 的末尾下标，就是 ans.size() - 1
所以代码变为
ans.get(ans.size() - 1 - level).add(root.val);
Copy
此外还有句代码要改。
if(ans.size()<=level){
ans.add(new ArrayList<>());
}
在添加当前 level 的第一个元素的时候，首先添加一个空列表到 ans 中
假设当前 level = 2，ans 中只添加了 level 是 0 和 1 的元素
ans [3] [9]
index 0 1
level 1 0
因为 level 是从右往左增加的，所以空列表要到 ans 的头部
ans [] [3] [9]
index 0 1 2
level 2 1 0
所以代码改成下边的样子
ans.add(0，new ArrayList<>());
Copy
综上，只要改了这两处就可以了。
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
DFS(root, 0, ans);
return ans;
}
private void DFS(TreeNode root, int level, List<List<Integer>> ans) {
if (root == null) {
return;
}
// 当前层数还没有元素，先 new 一个空的列表
if (ans.size() <= level) {
ans.add(0, new ArrayList<>());
}
// 当前值加入
ans.get(ans.size() - 1 - level).add(root.val);
DFS(root.left, level + 1, ans);
DFS(root.right, level + 1, ans);
}
Copy
解法二 BFS
102 题 从根节点往下走的代码贴过来。
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null)
return ans;
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size(); // 当前层元素的个数
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
TreeNode curNode = queue.poll();
if (curNode != null) {
subList.add(curNode.val);
queue.offer(curNode.left);
queue.offer(curNode.right);
}
}
if(subList.size()>0){
ans.add(subList);
}
}
return ans;
}
Copy
BFS相比于DFS要简单些，因为BFS是一次性把当前层的元素都添加到ans中，所以我们只需要改一句代码。
ans.add(subList);
Copy
改成添加到头部即可。
ans.add(0,subList);
Copy
再改个函数名字， 总体代码就是
public List<List<Integer>> levelOrderBottom(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null)
return ans;
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size(); // 当前层元素的个数
List<Integer> subList = new LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
TreeNode curNode = queue.poll();
if (curNode != null) {
subList.add(curNode.val);
queue.offer(curNode.left);
queue.offer(curNode.right);
}
}
if (subList.size() > 0) {
ans.add(0, subList);
}
}
return ans;
}
Copy
总
这道题依旧考层次遍历，只需要在 102 题的基础上，找到 level 和 index 的对应关系即可。此外，因为我们在头部添加元素，所以用链表会好一些。如果数组的话，还得整体后移才能添加新的元素。
