题目描述

给你一个二叉树，请你返回其按层序遍历得到的节点值。（即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,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轻松。
很必要的一点，就是学会使用两种及以上的语言来写算法。

其他题解

图片来源：微信公众号“看图学算法”
学习笔记，待补充…