Coding Interview Patterns Cheat Sheet (DRAFT) by radhabhala1

1. //Binary tree level traversal (LC102)
Create queue
add first element to the queue
while loop:(­until queue is empty)
forloop:for the length of queue
1. pop the first element of the queue
2. update output:
3. add children in the queue


public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        if(root==null)
            return result; 
       
        q.add(root);
        while(!q.isEmpty()){
            List<Integer> curList = new ArrayList<>();
            int lengthQueue = q.size();
            
            //empty the queue for the level
            // and insert the child of the elements in the queue
            for(int i =0; i<lengthQueue;i++){
                TreeNode curr = q.poll();
                curList.add(curr.val);
                if(curr.left != null)
                    q.add(curr.left);
                if(curr.right != null)
                    q.add(curr.right);                
            }
            result.add(curList);
        }
        
        return result;
    }

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;
        if (current.left != null) queue.add(current.left);
        if (current.right != null) queue.add(current.right);
    }
    return root;
}

LC78
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}