Binary Tree Right Side View

1package pkg5leetcode.official75;2 3/*4 * Binary Tree Right Side View | LC 1995 * APPROACH: BFS take last node each level.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class official75_LC199BinaryTreeRightSideView {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<Integer> rightSideView(TreeNode root) {20        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            for (int i = 0; i < size; i++) {27                TreeNode node = q.poll();28                if (i == size - 1) res.add(node.val);29                if (node.left != null) q.add(node.left);30                if (node.right != null) q.add(node.right);31            }32        }33        return res;34    }35 36    public static void main(String[] args) {37        TreeNode root = new TreeNode(1);38        root.left = new TreeNode(2); root.right = new TreeNode(3);39        root.left.right = new TreeNode(5); root.right.right = new TreeNode(4);40        check(rightSideView(root).equals(Arrays.asList(1,3,4)), "case1");41        TreeNode r2 = new TreeNode(1); r2.right = new TreeNode(3);42        check(rightSideView(r2).equals(Arrays.asList(1,3)), "case2");43        System.out.println("all tests passed");44    }45 46    static void check(boolean cond, String name) {47        if (!cond) throw new AssertionError("FAILED: " + name);48        System.out.println("  PASS " + name);49    }50}