# 20200109

https://ppt.cc/fO8Kex

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    helper(result, new ArrayList<>(), nums, 0);
    return result;
}    
[]
[], [1]
[], [1], [1, 2]
[], [1], [1, 2], [1, 2, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]
[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]
public void helper(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) {
    result.add(new ArrayList<>(tempList));
    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]); 
        helper(result, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:

Input: [1,2,3,4,5]

1
/ \
2 3
/ \
4 5

Output: [[4,5,3],[2],[1]]

Explanation:

1. Removing the leaves [4,5,3] would result in this tree:

1
/
2

2. Now removing the leaf [2] would result in this tree:

1

3. Now removing the leaf [1] would result in the empty tree:

[]

List<List<Integer>> leavesList = new ArrayList< List<Integer>>();
List<Integer> leaves = new ArrayList<Integer>();

while(root != null) {
if(isLeave(root, leaves))
root = null;
leavesList.add(leaves);
leaves = new ArrayList<Integer>();
}
return leavesList;
}

public boolean isLeave(TreeNode node, List<Integer> leaves) {

if (node.left == null && node.right == null) {
leaves.add(node.val);
return true;
}

if (node.left != null) {
if(isLeave(node.left, leaves)) node.left = null;
}

if (node.right != null) {
if(isLeave(node.right, leaves)) node.right = null;
}

return false;
}

public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
findLeavesHelper(list, root);
return list;
}

// return the level of root
private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
if (root == null) {
return -1;
}
// 1
int leftLevel = findLeavesHelper(list, root.left); // 1
int rightLevel = findLeavesHelper(list, root.right); // 0
int level = Math.max(leftLevel, rightLevel) + 1;
if (list.size() == level) { // 0
list.add(new ArrayList<>()); // [4, 5], [2], [1]
}
list.get(level).add(root.val); // [4, 5, 3]
root.left = null;
root.right = null;
return level;
}