#记录每一层的最后一个节点
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (root == null) {
return list;
}
Deque<TreeNode> queue = new ArrayDeque<>();
TreeNode t = root;
TreeNode endNode = root;// 记录本层最后一个节点
queue.offer(t);
List<Integer> res = new ArrayList<>();
while (!queue.isEmpty()) {
t = queue.poll();
// 记录
res.add(t.val);
if (t == endNode) {
// 本层最后一个节点弹出
list.add(res);
//res.clear();
//上面那么些是错的，因为这样会把加入list的List清除掉
res = new ArrayList<>();
}
if (t.left != null) {
queue.offer(t.left);
}
if (t.right != null) {
queue.offer(t.right);
}
// 维护endNode
if (t == endNode) {
// 当前队列的队尾就是本层的最后一个节点
endNode = queue.peekLast();
}
}
return list;
}
记录每一层的节点数
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if (root == null)
return list;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while (!que.isEmpty()) {
List<Integer> res = new ArrayList<>();
int len = que.size();// 记录这一层的长度
while (len-- > 0) {
TreeNode tempNode = que.poll();
res.add(tempNode.val);
if (tempNode.left != null) {
que.offer(tempNode.left);
}
if (tempNode.right != null) {
que.offer(tempNode.right);
}
}
list.add(res);
}
return list;
}
递归
List<List<Integer>> list = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
func(root, 0);// 根节点在第0层
return list;
}
public void func(TreeNode t, int deep) {
if (t == null) {
return;
}
if (list.size() < deep + 1) {
// 为新的一层首先存储一个空的list
List<Integer> res = new ArrayList<>();
list.add(res);
}
list.get(deep).add(t.val);
func(t.left, deep + 1);
func(t.right, deep + 1);
}
java中有一个特别需要注意的点是，必须新建
