题目描述
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
题解
我想用栈来实现，但是发现有些问题。日后再补充。
现在，干脆就直接学习学习他人的优秀算法，顺便记录一下感想。
该算法题解来自~
微信公众号：看图学算法
链接：https://mp.weixin.qq.com/s/oI_pmqvaA9AFQUPxKX13vw
用广度优先BFS处理是很直观的，可以想象成是一把刀横着切割了每一层，但是深度优先遍历就不那么直观了。
我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子。
田字形的每一层就对应一个list。
按照深度优先DFS的处理顺序，会先访问节点1，再访问节点2，接着是节点3。
之后是第二列的4和5，最后是第三列的6。
每次递归的时候都需要带一个index(表示当前的层数)，也就对应那个田字格子中的第几行，如果当前行对应的list不存在，就加入一个空list进去。
动态演示如下：
代码
import java.util.*;
class Solution {
void dfs(int index,TreeNode root, List<List<Integer>> res) {
//每次递归的时候都需要带一个index(表示当前的层数)
//如果当前行对应的list不存在，就加入一个空list进去。
//假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
if(res.size()<index) {
res.add(new ArrayList<Integer>());
}
//将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
//res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
res.get(index-1).add(root.val);
//递归的处理左子树，右子树，同时将层数index+1
if(root.left!=null) {
dfs(index+1, root.left, res);
}
if(root.right!=null) {
dfs(index+1, root.right, res);
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
if(root==null) {
return new ArrayList<List<Integer>>();
}
//用来存放最终结果
List<List<Integer>> res = new ArrayList<List<Integer>>();
dfs(1,root,res);
return res;
}
}
时间复杂度:O(N)
空间复杂度:O(h)，h是树的高度**
心得体会
首先，我绝对不会想到用list，因为我对集合一是不敏感，二是基础知识掌握不多。
第二点是，灵活性的不足，即使我想不到list，但是我也没想过“我们开下脑洞，把这个二叉树的样子调整一下，摆成一个田字形的样子”🤣
先前写算法基本都是用C来写，偶尔用C++。
有的题目用C写起来轻松，但是有的却用Java轻松。
很必要的一点，就是学会使用两种及以上的语言来写算法。
其他题解
图片来源：微信公众号“看图学算法”
学习笔记，待补充...
京公网安备 11010502036488号