LeetCode 102 Binary Tree Level Order Traversal

思路

BFS，但是需要每次将下一层所有节点都放入queue中

复杂度

时间复杂度O(n)
空间复杂度O(n)

代码

/*** Definition of TreeNode:* public class TreeNode {* public int val;* public TreeNode left, right;* public TreeNode(int val) {* this.val = val;* this.left = this.right = null;* }* }*/public class Solution {
    /*** @param root: A Tree* @return: Level order a list of lists of integer*/public List<List<Integer>> levelOrder(TreeNode root) {
    // write your code hereList<List<Integer>> res = new ArrayList<>();Queue<TreeNode> queue = new LinkedList<>();if (root == null) {
    return res;}queue.offer(root);while (!queue.isEmpty()) {
    int size = queue.size();List<Integer> value = new ArrayList<>();for (int i = 0; i < size; i++) {
    TreeNode t = queue.poll();value.add(t.val);if (t.left != null) {
    queue.offer(t.left);}if (t.right != null) {
    queue.offer(t.right);}}res.add(new ArrayList(value));}return res;}
}