解题思路:层序遍历。比较有技巧性的地方就在于判断什么时候完成了一层的遍历。 这里的解决方案是每遍历完一层就在末尾放入一个null,当遍历到null 的时候说明这一层就遍历结束了,当队列中只有一个元素的时候就说明整个按层遍历结束了。
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
// write code here
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return list;
}
// 用LinkedList 做队列
List<TreeNode> queue = new LinkedList();
queue.add(root);
queue.add(null);
while(queue.size()>1) {
ArrayList<Integer> l = new ArrayList<Integer>();
TreeNode node;
while((node = queue.remove(0))!=null) {
l.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
// 每遍历完一层往队尾插入一个层的结束标志
queue.add(null);
list.add(l);
}
return list;
}
}```