PattySung

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] Example 2:

Input: root = [1] Output: [[1]] Example 3:

Input: root = [] Output: []

<解題>

使用一個隊列（Queue）來幫助進行層序遍歷，將根節點添加到隊列中
res，用於存儲遍歷的結果
level: 存每層的節點
看是否當前節點有左右節點，有的話加入queue->繼續遍歷


class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        List<List<Integer>> res = new ArrayList<>();

        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode curr = queue.poll();
                level.add(curr.val);
                if(curr.left!= null) queue.offer(curr.left);
                if(curr.right!= null) queue.offer(curr.right);
            }
            res.add(level);
        }
        return res;
    }
}

Time: O(N) Space: O(H)

和 199. Binary Tree Right Side View 做比較

Leetcode-102. Binary Tree Level Order Traversal

<解題>