Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
public List<List<Integer>> levelOrder(TreeNode root) {
List<Integer> list1 = new ArrayList<Integer>();
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (root == null)
return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int sum = 1, i = 1;
while (!queue.isEmpty()) {
TreeNode t1 = queue.poll();
System.out.println(t1.val);
list1.add(t1.val);
if (sum == Math.pow(2, i) - 1) {
list.add(list1);
list1 = new ArrayList<Integer>();
i++;
}
if (t1.left != null)
queue.add(t1.left);
if (t1.right != null)
queue.add(t1.right);
sum += 2;
}
if (!list1.isEmpty()) {
list.add(list1);
}
return list;
}这个是我最开始的思路，我想用每一层sum计数，然后sum得到2的层次方减一就是在那一层这样的方法来控制每次list1要装几次。第一个错误，就是List1每次必须是new出来，用clear不行的；第二个错误，就是如果一个父节点压根就没有右节点或者没有左节点，那么上面的判断方式失效。比如：[3,9,20,null,null,15,7]。
后来我考虑到，每次加到队列中的元素其实就是那一层的元素，用queue的size()方法就行。这个要注意我标识在代码中了。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
if (root == null)
return list;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()) {
List<Integer> list1 = new ArrayList<Integer>();
//这个注意，一定要先记录下来，不然底下size会变的
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode t1 = queue.poll();
list1.add(t1.val);
if (t1.left != null)
queue.add(t1.left);
if (t1.right != null)
queue.add(t1.right);
}
list.add(list1);
}
return list;
}
这里我又去网上找了几种算法，第一种跟我基本一样。其余的大家可以多作了解，我有时间再看，先贴上来。
// version 1: BFS
public class Solution {
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList result = new ArrayList();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
ArrayList<Integer> level = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode head = queue.poll();
level.add(head.val);
if (head.left != null) {
queue.offer(head.left);
}
if (head.right != null) {
queue.offer(head.right);
}
}
result.add(level);
}
return result;
}
}
// version 2: DFS
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return results;
}
int maxLevel = 0;
while (true) {
ArrayList<Integer> level = new ArrayList<Integer>();
dfs(root, level, 0, maxLevel);
if (level.size() == 0) {
break;
}
results.add(level);
maxLevel++;
}
return results;
}
private void dfs(TreeNode root,
ArrayList<Integer> level,
int curtLevel,
int maxLevel) {
if (root == null || curtLevel > maxLevel) {
return;
}
if (curtLevel == maxLevel) {
level.add(root.val);
return;
}
dfs(root.left, level, curtLevel + 1, maxLevel);
dfs(root.right, level, curtLevel + 1, maxLevel);
}
}
// version 3: BFS. two queues
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
ArrayList<TreeNode> Q1 = new ArrayList<TreeNode>();
ArrayList<TreeNode> Q2 = new ArrayList<TreeNode>();
Q1.add(root);
while (Q1.size() != 0) {
ArrayList<Integer> level = new ArrayList<Integer>();
Q2.clear();
for (int i = 0; i < Q1.size(); i++) {
TreeNode node = Q1.get(i);
level.add(node.val);
if (node.left != null) {
Q2.add(node.left);
}
if (node.right != null) {
Q2.add(node.right);
}
}
// swap q1 and q2
ArrayList<TreeNode> temp = Q1;
Q1 = Q2;
Q2 = temp;
// add to result
result.add(level);
}
return result;
}
}
// version 4: BFS, queue with dummy node
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null) {
return result;
}
Queue<TreeNode> Q = new LinkedList<TreeNode>();
Q.offer(root);
Q.offer(null); // dummy node
ArrayList<Integer> level = new ArrayList<Integer>();
while (!Q.isEmpty()) {
TreeNode node = Q.poll();
if (node == null) {
if (level.size() == 0) {
break;
}
result.add(level);
level = new ArrayList<Integer>();
Q.offer(null); // add a new dummy node
continue;
}
level.add(node.val);
if (node.left != null) {
Q.offer(node.left);
}
if (node.right != null) {
Q.offer(node.right);
}
}
return result;
}
}
