题目:
题解:
1. 迭代实现:
2. 递归实现:
代码:
1. 迭代实现:
/** * code102 */
import java.util.*;
public class code102 {
public static List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> res = new ArrayList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
// 将根节点放入队列中,然后不断遍历队列
queue.offer(root);
while (!queue.isEmpty()) {
// 获取当前队列的长度,这个长度相当于,当前这一层的节点个数
int size = queue.size();
List<Integer> tmp = new ArrayList<>();
// 将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中
// 如果节点的左/右子树不为空,也放入队列中
for (int i = 0; i < size; i++) {
TreeNode t = queue.poll();
tmp.add(t.val);
if (t.left != null) {
queue.offer(t.left);
}
if (t.right != null) {
queue.offer(t.right);
}
}
// 将临时list加入最终返回结果中
res.add(tmp);
}
return res;
}
public static void main(String[] args) {
System.out.println("***************************************");
Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
TreeNode tree = ConstructTree.constructTree(nums);
TreeOperation.show(tree);
System.out.println("***************************************");
List<List<Integer>> list = levelOrder(tree);
System.out.println(list.toString());
System.out.println("***************************************");
}
}
注:
在Java中,Queue是一个接口,LinkedList(链表)实现了该接口。ArrayList实现的是List接口,没有实现Queue接口,不能用ArrayList初始化Queue。另外LinkedList和ArrayList都是List接口的具体实现,一个类似链表,一个类似动态数组。
可以参考这个图片中的Java集合类。
2. 递归实现:
/** * code102 */
import java.util.*;
public class code102 {
public static 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;
}
public static void dfs(int index, TreeNode root, List<List<Integer>> res) {
// 假设res是[ [1],[2,3] ], index是3,就再插入一个空list放到res中,index表示当前的层数
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 static void main(String[] args) {
System.out.println("***************************************");
Integer nums[] = { 3, 9, 20, null, null, 15, 7 };
TreeNode tree = ConstructTree.constructTree(nums);
TreeOperation.show(tree);
System.out.println("***************************************");
List<List<Integer>> list = levelOrder(tree);
System.out.println(list.toString());
System.out.println("***************************************");
}
}