题目描述
思路
方法一：递归
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
level(root, 0, res);
return res;
}
private void level(TreeNode node, int curLevel, List<List<Integer>> res) {
if (node == null) return;
if (res.size() == curLevel) {
List<Integer> list = new ArrayList<>();
list.add(node.val);
res.add(list);
} else {
res.get(curLevel).add(node.val);
}
level(node.left, curLevel + 1, res);
level(node.right, curLevel + 1, res);
}
}
class Node{
TreeNode node;
int level;
Node (TreeNode node, int level) {
this.node = node;
this.level = level;
}
}
方法二：迭代
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
if (root == null) return res;
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i ++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(level);
}
return res;
}
}