Binary Tree Level Order Traversal

1package pkg5leetcode.blind75;2 3/*4 * Binary Tree Level Order Traversal | LC 1025 * APPROACH: BFS queue processes level by level.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class blind75_LC102BinaryTreeLevelOrderTraversal {11    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */12 13    static class TreeNode {14        int val;15        TreeNode left, right;16        TreeNode(int val) { this.val = val; }17    }18 19    static List<List<Integer>> levelOrder(TreeNode root) {20        List<List<Integer>> res = new ArrayList<>();21        if (root == null) return res;22        Deque<TreeNode> q = new ArrayDeque<>();23        q.add(root);24        while (!q.isEmpty()) {25            int size = q.size();26            List<Integer> level = new ArrayList<>();27            for (int i = 0; i < size; i++) {28                TreeNode node = q.poll();29                level.add(node.val);30                if (node.left != null) q.add(node.left);31                if (node.right != null) q.add(node.right);32            }33            res.add(level);34        }35        return res;36    }37 38    public static void main(String[] args) {39        TreeNode root = new TreeNode(3);40        root.left = new TreeNode(9);41        root.right = new TreeNode(20);42        root.right.left = new TreeNode(15);43        root.right.right = new TreeNode(7);44        List<List<Integer>> r = levelOrder(root);45        check(r.size() == 346                && r.get(0).equals(Arrays.asList(3))47                && r.get(1).equals(Arrays.asList(9, 20))48                && r.get(2).equals(Arrays.asList(15, 7)), "case1");49        check(levelOrder(null).isEmpty(), "case2");50        System.out.println("all tests passed");51    }52 53    static void check(boolean cond, String name) {54        if (!cond) throw new AssertionError("FAILED: " + name);55        System.out.println("  PASS " + name);56    }57}