# Count Univalue Subtrees

Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:
Given binary tree,

```              5
/ \
1   5
/ \   \
5   5   5
```

return `4`.

Solution:

```public int countUnivalSubtrees(TreeNode root) {
int[] count = new int[1];
isUnivalSubtrees(root, count);
return count[0];
}

public boolean isUnivalSubtrees(TreeNode root, int[] count) {
if (root == null) {
return false;
}
boolean left = isUnivalSubtrees(root.left, count);
boolean right = isUnivalSubtrees(root.right, count);
if (!left && !right) {
if (root.left == null && root.right == null) {
count[0]++;
return true;
}
} else if (left && right) {
if (root.left.val == root.val && root.right.val == root.val) {
count[0]++;
return true;
}
} else if (left && !right) {
if (root.right == null && root.left.val == root.val) {
count[0]++;
return true;
}
} else if (!left && right) {
if (root.left == null && root.right.val == root.val) {
count[0]++;
return true;
}
}
return false;
}```
Share

# Combination Sum

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

For example, given candidate set `2,3,6,7` and target `7`,
A solution set is:
`[7]`
`[2, 2, 3]`

Example

given candidate set `2,3,6,7` and target `7`,
A solution set is:
`[7]`
`[2, 2, 3]`

Note

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

Solution: Subsets 变种题 DFS

O(2^n) time

```public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
if (candidates == null) {
return result;
}
Arrays.sort(candidates);
combinationSumHelper(new ArrayList<Integer>(), 0, candidates, target, result);

return result;
}

public void combinationSumHelper(ArrayList<Integer> curr, int index, int[] candidates, int target, List<List<Integer>> result) {
if (target == 0) {
return;
}
if (index >= candidates.length) {
return;
}
for (int i = index; i < candidates.length; i++) {
if (candidates[i] <= target) {
combinationSumHelper(curr, i, candidates, target - candidates[i], result);
curr.remove(curr.size() - 1);
}
}
}```

# Palindrome Partitioning

#### Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example

given s = `"aab"`,
Return

```  [
["aa","b"],
["a","a","b"]
]```

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

```public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
partitionHelper(s, new ArrayList<String>(), result);
return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
if (s.length() == 0) {
return;
}
for (int i = 0; i < s.length(); i++) {
String currString = s.substring(0, i + 1);
if (isPalindrome(currString)) {
partitionHelper(s.substring(i + 1), curr, result);
curr.remove(curr.size() - 1); //important
}
}
}

public boolean isPalindrome(String s) {
int start = 0;
int end = s.length() - 1;
while (start <= end) {
if (s.charAt(start) != s.charAt(end)) {
return false;
}
start++;
end--;
}
return true;
}```

# N-Queens I &&II

N-Queens I

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Example

There exist two distinct solutions to the 4-queens puzzle:

[

[“.Q..”, // Solution 1

“…Q”,

“Q…”,

“..Q.”],

[“..Q.”, // Solution 2

“Q…”,

“…Q”,

“.Q..”]

]

Solution1: Recursion DFS, Permutation模板，判断条件换一下

```ArrayList<ArrayList<String>> solveNQueens(int n) {
ArrayList<ArrayList<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result;
}

//DFS
public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<ArrayList<String>> result) {
if (row == chessBoard.length) {
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}

public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}

public ArrayList<String> toStringList(int[][] chessBoard) {
ArrayList<String> result = new ArrayList<>();
for (int i = 0; i < chessBoard.length; i++) {
StringBuilder row = new StringBuilder();
for (int j = 0; j < chessBoard[i].length; j++) {
if (chessBoard[i][j] == 0) {
row.append('.');
} else {
row.append('Q');
}
}
}
return result;
}```

Solution 2. Non-Recursive

N-Queens II

Now, instead outputting board configurations, return the total number of distinct solutions.

Example

For n=4, there are 2 distinct solutions.

Solution 1. Recursive. DFS

Solution 1. Recursive

```public int totalNQueens(int n) {
ArrayList<Integer> result = new ArrayList<>();
if (n <= 0) {
return 0;
}
int[][] chessBoard = new int[n][n];
solveNQueensHelper(chessBoard, 0, result);
return result.size();
}

public void solveNQueensHelper(int[][] chessBoard, int row, ArrayList<Integer> result) {
if (row == chessBoard.length) {
return;
}
for (int col = 0; col < chessBoard[row].length; col++) {
if (isValid(chessBoard, row, col)) {
chessBoard[row][col] = 1;
solveNQueensHelper(chessBoard, row + 1, result);
chessBoard[row][col] = 0;
}
}
}

public boolean isValid(int[][] chessBoard, int row, int col) {
for (int i = 1; i <= row; i++) {
if ((col - i >= 0 && chessBoard[row - i][col - i] == 1) ||
(col + i < chessBoard.length && chessBoard[row - i][col + i] == 1) ||
chessBoard[row - i][col] == 1) {
return false;
}
}
return true;
}```

Solution 2. Non-Recursive

# k Sum II

#### k Sum II

Given n unique integers, number k (1<=k<=n)  and target. Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k=2, target=5, [1,4] and [2,3] are possible solutions

Solutions: DFS

Time Complexity?

```    public ArrayList < ArrayList < Integer >> kSumII(int A[], int k, int target) {
ArrayList < ArrayList < Integer >> result = new ArrayList < > ();
if (A == null) {
return result;
}
kSumIIHelper(new ArrayList < Integer > (), 0, A, k, target, result);
return result;
}

public void kSumIIHelper(ArrayList < Integer > curr, int index, int A[], int k,
int target, ArrayList < ArrayList < Integer >> result) {
if (curr.size() == k) {
if (target == 0) {
}
return;
}
for (int i = index; i < A.length; i++) {
kSumIIHelper(curr, i + 1, A, k, target - A[i], result);
curr.remove(curr.size() - 1);
}
}```

# Convert Sorted List to Binary Search Tree

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

```public TreeNode sortedListToBST(ListNode head) {
return null;
}
TreeNode root = new TreeNode(mid.val);
ListNode midPost = mid.next;
}
root.right = sortedListToBST(midPost);

return root;

}

}