DFS
Find Optimal Solution during Bottom Up of DFS
If the problem solution(s) might exist in the subtree structures, we can't rely on the return value from DFS. One way we can do is to check (find max) the solutions in the subtrees while we bubble up from the bottom of the tree (post-order exit time). What DFS returns from sub-problems should be some information e.g. depth that we can leverage to calculate the optimal solution while bottom up.
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
class Solution {
private int max=0;
public int longestUnivaluePath(TreeNode root) {
depthUniVal(root);
return max;
}
public int depthUniVal(TreeNode root) {
if(root==null) return 0;
int l = depthUniVal(root.left);
int r = depthUniVal(root.right);
if(root.left!=null && root.left.val!=root.val ) l=0;
if(root.right!=null && root.right.val!=root.val ) r=0;
max = Math.max(max, l+r);
return Math.max(l,r)+1;
}
}
Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of anyoneof them.
Two trees are duplicate if they have the same structure with same node values.
Example 1:
1
/ \
2 3
/ / \
4 2 4
/
4
The following are two duplicate subtrees:
2
/
4
and
4
Therefore, you need to return above trees' root in the form of a list.
This question more or less uses the same traversal methodology. The only difference is not to calculate the path length, but to check for string/sequence of nodes for duplicated subtree. But note two techniques:
- Use HashMap to count the duplicated subtree. Since we just add one to the result if there are multiple duplicates, add when the count is 1.
- We better add "(" ")" to serialise the node string sequence. We can't ensure the traversal could produce the unique string sequence especially when the node label could be the same.
DFS Variations
Connect Same Level Nodes
116. Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set toNULL. Initially, all next pointers are set toNULL.
Hints: use previous level connecting pointers to access next level nodes.
Return Result in Pair/Data Object
Sometimes, we may need two piece of information from DFS of next level. We may return the results in pair. For example,
public int[] findLongestConsecutive(TreeNode root) {}
549. Binary Tree Longest Consecutive Sequence II
Two Subproblem Scenario Solutions
Some problems have some conditions/criteria/constraints for the way we calculate the solution, particularly in the game playing implicit DFS. Therefore, when post-order exist from subproblem (subtree), we have two possible solutions. We keep maximising the solution based on constraints when bubbling up from DFS.
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
Example 1:
3
/ \
2 3
\ \
3 1
class Solution {
public int rob(TreeNode root) {
int[] ans = find(root);
return Math.max(ans[0], ans[1]);
}
public int[] find(TreeNode root) {
if(root==null) return new int[]{0,0};
int[] left = find(root.left);
int[] right = find(root.right);
int withoutRoot = left[0] + right[0];
int max = Math.max(root.val+left[1]+right[1], withoutRoot);
return new int[]{max, withoutRoot};
}
}
Implicit DFS
248. Strobogrammatic Number III
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.
For example,
Given low = "50", high = "100", return 3. Because 69, 88, and 96 are three strobogrammatic numbers.
Note:
Because the range might be a large number, the low and high numbers are represented as string.
public int dfs(String low, String high, char[] c, int left, int right) {
if(left>right) { //base case
String s = new String(c);
if ((s.length() == low.length() && s.compareTo(low) < 0) ||
(s.length() == high.length() && s.compareTo(high) > 0)) {
return 0;
} else {
return 1;
}
}
int count = 0;
for(char[] pair: pairs) {
c[left]=pair[0]; c[right]=pair[1];
if(c.length!=1 && c[0] == '0') continue;
if(left==right && pair[0]!=pair[1]) continue;
count+=dfs(low, high, c, left+1, right-1);
}
return count;
}
Backtracking
Backtracking is a special kind of DFS with states/content restoration.
- For some problem DFS requires visited marking, we can utilise the input data storage to do the marking because backtracking will restore the content/status anyway. In this way, no need to create visited[] array to do the marking.
- If we really need to create space for visited marking, sometimes, it could be HashMap/HashSet/Array.
- Be careful with the ending conditions (base cases), make sure it has no logic flaw.
char c = board[i][j];
board[i][j] = '#'; //board[][] is input data, we use # to mark visited
Node next = root.children.get(c);
if(next!=null) {
if(next.word!=null) results.add(next.word);
findWords(board, i-1, j, next, results);
findWords(board, i+1, j, next, results);
findWords(board, i, j-1, next, results);
findWords(board, i, j+1, next, results);
}
board[i][j] = c; //backtracking restore status / content
Backtracking for Combinations
Sometimes the elements to choose from to form the combinations contains duplicates. In this case, let say there are three 1s. Your choice could be having no 1, one 1, two 1s or three 1s. And backtracking on these choices... if you don't do it such a way, there could be duplicate combinations in the result set, as these duplicates were considered seperately.
for(int i=index; i<candidates.length && target>=candidates[i]; i++) {
int count=1;
while(i+1<candidates.length && candidates[i+1]==candidates[i]) {
count++;
i++;
}
for(int k=1; k<=count; k++) {
list.add(candidates[i]);
findCombination(result, list, candidates, target-candidates[i]*k, i+1);
}
list.subList(list.size()-count, list.size()).clear();
}
In some combination problem, we want to make sure we don't have duplicated combinations, e.g. 2 2 3 vs 2 3 2, we make sure the sequence is increasing... we might pass in a parameter of previous ending number to make sure that.
class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> result = new ArrayList<>();
//to eliminate duplicate, we need to have the sequence in increasing order, so need the start parameter
getFactors(result, new ArrayList<>(), n, 2);
return result;
}
public void getFactors(List<List<Integer>> result, List<Integer> list, int n, int start) {
for(int i=start; i<=Math.sqrt(n); i++) { //possible factors of n is 2 .. sqrt(n)
if(n%i==0) {
list.add(i); //if we take factor i
int x = n/i;
List<Integer> newList = new ArrayList<>(list);
newList.add(x); result.add(newList);
getFactors(result, list, x, i);
list.remove(list.size()-1); //if we don't take factor i
}
}
}
}
Try out different backtracking when I have time!!!
Multiple Iterations Backtracking
698. Partition to K Equal Sum Subsets
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:
1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.
class Solution {
/** 0-1 Knapsack Problem k times doesn't work because we can't actually mark which elements are taken for an iteration*/
//we can do special form of backtracking
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int num: nums) {
sum += num;
}
if(sum%k != 0 ) return false;
sum /= k;
return canPartition(nums, new boolean[nums.length], k, 0, 0, sum);
}
public boolean canPartition(int[] nums, boolean[] taken, int k, int index, int currSum, int sum) {
if(k==1) return true;
if(currSum>sum) return false; //early termination
if(currSum==sum) {
return canPartition(nums, taken, k-1, 0, 0, sum);
}
for(int i=index; i<nums.length; i++) {
if(!taken[i]) {
taken[i] = true;
if(canPartition(nums, taken, k, i+1, currSum+nums[i], sum)){
return true;
}
taken[i] = false;
}
}
return false;
}
}
Iterative Deepening Depth First Search(IDDFS)
IDDFS is best suited for a complete infinite tree.
If there is a node close to root, but not in first few subtrees explored by DFS, then DFS reaches that node very late. Also, DFS may not find shortest path to a node (in terms of number of edges).
The space required by DFS is O(d) where d is depth of tree, but space required by BFS is O(n) where n is number of nodes in tree (Why? Note that the last level of tree can have around n/2 nodes and second last level n/4 nodes and in BFS we need to have every level one by one in queue).
# IDDFS to search if target is reachable from v.
# It uses recursive DLS()
def IDDFS(self,src, target, maxDepth):
# Repeatedly depth-limit search till the
# maximum depth
for i in range(maxDepth):
if (self.DLS(src, target, i)):
return True
return False
The last (or max depth) level is visited once, second last level is visited twice, and so on. It may seem expensive, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level. So it does not matter much if the upper levels are visited multiple times.