<commit_before>package fundamentals.tree.traversal.level.lc102_binarytreelevelordertraversal;

import fundamentals.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 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], return its level order traversal as:
 * [
 *  [3],
 *  [9,20],
 *  [15,7]
 * ]
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> vals = new ArrayList<>();
        if (root == null) {
            return vals;<commit_msg>leetcode-102 binary tree level order traversal<commit_after>package fundamentals.tree.traversal.level.lc102_binarytreelevelordertraversal;

import fundamentals.tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 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], return its level order traversal as:
 * [
 *  [3],
 *  [9,20],
 *  [15,7]
 * ]
 */
public class Solution {

    // My 2nd: O(N) time, O(width) space
    public List<List<Integer>> levelOrder2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }

        List<List<Integer>> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>(size);
            while (size-- > 0) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(level);
        }
        return result;
    }

    // Interesting DFS solution from leetcode discuss
    // This is much faster than BFS version?! Beat 85%!!!
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        doLevelOrder(result, root, 0);
        return result;
    }

    private void doLevelOrder(List<List<Integer>> result, TreeNode root, int height) {
        if (root == null) {
            return;
        }

        if (result.size() <= height) {
            result.add(new ArrayList<>());
        }
        result.get(height).add(root.val);
        doLevelOrder(result, root.left, height + 1);
        doLevelOrder(result, root.right, height + 1);
    }

    // My 1st
    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> vals = new ArrayList<>();
        if (root == null) {
            return vals;
{'fraction_non_alphanumeric': 0.12996632996632998, 'fraction_numerical': 0.015824915824915825, 'mean_word_length': 2.3608597285067874, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5331492', 'n_tokens_mistral': 912, 'n_tokens_neox': 867, 'n_words': 237}