递推
package leetcode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public List> levelOrder(TreeNode root) {
List> ls = new ArrayList>();
Queue queue = new LinkedList();
if (root == null)
return ls;
queue.add(root);
while (!queue.isEmpty()) { // 结合数学运算
int len = queue.size();
List l = new ArrayList();
for (int i = 0; i < len; i++) { //len用于记录queue.size() 不会被for 里面的代码所影响 这道题 很妙
TreeNode T = queue.poll();
if (T.left != null)
queue.add(T.left);
if (T.right != null)
queue.add(T.right);
l.add(T.val);
}
ls.add(l);
}
return ls;
}
}
解法二
递归
class Solution {
public List> levelOrder(TreeNode root) {
List> list = new ArrayList();
levelOrder(root, list, 0);
return list;
}
public void levelOrder(TreeNode root, List> list, int level){
if(root != null){
if(level > list.size() - 1){
List nodes = new ArrayList();
list.add(nodes);
}
list.get(level).add(root.val);
levelOrder(root.left, list, level + 1);
levelOrder(root.right, list, level + 1);
}
}
}