• [ ] cheetsheet: queue

Level order traversal

Iterative version

• remember to check for null before putting into queue
• don’t iterative on q.size() directly as the number is changing (rather, save it into a local variable size before the for loop

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.add(root);

        while (!q.isEmpty()) {
            int size = q.size();
            List<Integer> listLevel = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();

                listLevel.add(cur.val);
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
            }
            res.add(listLevel);

        }

        return res;
    }
}

Recursive version

• remember to return directly when cur is null
• check if the result list res has enough elements to match the depth (only need to check for size() == depth which requires one more level)

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelHelper(root, res, 0);
        return res;
    }

    public void levelHelper(TreeNode cur, List<List<Integer>> res, int depth) {
        if (cur == null) return;

        List<Integer> curLevelList;
        if (res.size() == depth) {
            curLevelList = new ArrayList<Integer>();
            res.add(curLevelList);
        } else {
            curLevelList = res.get(depth);
        }

        curLevelList.add(cur.val);
        levelHelper(cur.left, res, depth+1);
        levelHelper(cur.right, res, depth+1);
    }
}

102. Binary Tree Level Order Traversal

(above)

107. Binary Tree Level Order Traversal II

• Can do like #102, and reverse the list at the end
• Alternatively, can use LinkedList to insert at the head

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();

        if (root != null) q.add(root);

        while (!q.isEmpty()) {
            List<Integer> curLevel = new ArrayList<>();
            int count = q.size();

            while (count > 0) {
                TreeNode cur = q.poll();
                curLevel.add(cur.val);
                if (cur.left != null) q.add(cur.left);
                if (cur.right != null) q.add(cur.right);
                count--;
            }
            res.add(curLevel);
        }

        Collections.reverse(res);
        return res;

    }
}

199. Binary Tree Right Side View

• for each level, get the rightmost element (i.e. last element in the levelNode list) and add to the result list res
• iterate over levelNode and add their children (if not null) to nextLevelNode; when done, assign the nextLevelNode list to levelNode and enter the next iteration
  • easier than using one single queue

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        List<TreeNode> levelNode = new ArrayList<>();
        if (root != null) levelNode.add(root);

        while (!levelNode.isEmpty()) {
            // each loop is one depth/level, no need to count
            res.add(levelNode.getLast().val);

            List<TreeNode> nextLevelNode = new ArrayList<>();
            for (TreeNode node : levelNode) {
                if (node.left != null) nextLevelNode.add(node.left);
                if (node.right != null) nextLevelNode.add(node.right);
            }
            levelNode = nextLevelNode;
        }

        return res;
    }
}