Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution: to generate all unique BSTs, we should generate the root from 1 to n, and generate its left subtree from 0 to i-1 and for each left subtree, we generate the right subtree from i+1 to n recursively. Note: this is a Binary Search Tree, so that we must make sure that all nodes whose values are smaller than root must be in the left subtree of the root, and all nodes whose values are larger than root must be in the right subtree of the root.

Java语言: UniqueBinarySearchTreesII

01 public ArrayList<TreeNode> generateTrees(int n) {
02     ArrayList<Integer> num=new ArrayList<Integer>();
03     for(int i=1;i<=n;i++)
04     {
05         num.add(i);
06     }
07     return generateTree(num,0,n-1);
08 }
09 
10 public ArrayList<TreeNode> generateTree(ArrayList<Integer> num, int start, int end)
11 {
12     ArrayList<TreeNode> results=new ArrayList<TreeNode>();
13     if(start>end)
14     {
15         TreeNode n=null;          
16         results.add(n);
17         return results;
18     }
19     for(int i=start;i<=end;i++)
20     {
21         ArrayList<TreeNode> leftTrees=generateTree(num, start, i-1);
22         for(int j=0;j<leftTrees.size();j++)
23         {
24             TreeNode leftChild=leftTrees.get(j);
25             ArrayList<TreeNode> rightTrees=generateTree(num, i+1, end);
26             for(int k=0;k<rightTrees.size();k++)
27             {
28                 TreeNode rightChild=rightTrees.get(k);
29                 TreeNode root=new TreeNode(num.get(i));
30                 root.left=leftChild;
31                 root.right=rightChild;
32                 results.add(root);
33             }
34         }
35     }
36     return results;
37 }

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution: treat each cell as a node of a graph, and its four cells (up, down, left, right) as neighbors. Use DFS, and use a visited array to mark if a node has been already visited. Starting a DFS from every cell of the board. If find, return true.

Java语言: WordSearch

01 public boolean exist(char[][] board, String word) {
02     int numRows=board.length;
03     int numCols=board[0].length;      
04     boolean [][]visited=new boolean[numRows][numCols];
05     for(int i=0;i<numRows;i++)
06     {
07         for(int j=0;j<numCols;j++)
08         {
09             //DFS starting from each cell
10             if(exist(board, i, j, 0, visited, word))
11                 return true;
12             //reset visited    
13             visited=new boolean[numRows][numCols];
14         }
15     }
16     return false;
17 }
18 
19 //DFS for substring starting at position i of word
20 public boolean exist(char[][] board, int row, int col, int i, boolean[][]visited, String word)
21 {
22     if(i==word.length())
23     {
24         return true;
25     }
26     if(row<0||row>=board.length||col<0 || col>=board[0].length)
27     {
28         return false;
29     }
30     if(!visited[row][col])
31     {
32         //set the current position of board as visited
33         if(board[row][col]==word.charAt(i))
34         {
35             visited[row][col]=true;
36             //DFS on its four neighbor
37             boolean case1=exist(board, row+1, col, i+1, visited, word);
38             boolean case2=exist(board, row-1, col, i+1, visited, word);
39             boolean case3=exist(board, row, col+1, i+1, visited, word);
40             boolean case4=exist(board, row, col-1, i+1, visited, word);              
41             return case1||case2||case3||case4;              
42         }          
43     }
44     return false;
45 }

Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution: make the last element of the postorder array as the root, then find the root value in the inorder array. Partition the inorder array into left and right parts. Call the buildTree function recursively. Very similar to the "Construct Binary Tree from Preorder and Inorder Traversal" problem.

Java语言: BuildTreeInorderPostorder

01 public TreeNode buildTree(int[] inorder, int[] postorder) {
02     int length=inorder.length;
03     return buildTree(inorder, 0, length-1, postorder, 0, length-1);
04 }
05 public TreeNode buildTree(int[] inorder, int start1, int end1, int []postorder, int start2, int end2)
06 {
07     if(start1>end1)
08         return null;
09     int value = postorder[end2];
10     int index = search(inorder, start1, end1, value);
11     TreeNode root = new TreeNode(value);
12     TreeNode left=buildTree(inorder, start1, index-1, postorder, start2, start2+index-start1-1);
13     TreeNode right=buildTree(inorder,index+1,end1,postorder, end2-(end1-index),end2-1);
14     root.left=left;
15     root.right=right;
16     return root;
17 }
18 
19 public int search(int[] array, int start, int end, int target)
20 {
21     for(int i=start;i<=end; i++)
22     {
23         if(array[i]==target)
24             return i;
25     }
26     return -1;
27 }

The Width of a Binary Tree

The width of a binary tree is defined as the maximum number of nodes of the same level. Assume a binary tree is like

        1

     /    \

   2       3

 /   \    /  \

4    5   6    7

Then the width of the tree is 4.

Write an algorithm to get the width of a binary tree.

Hint: a Breadth-First Search method may come to your mind immediately. However, can you use Depth First Search?

Solution: do a pre-order traversal. Using an array to keep track of the number of nodes in each level. When you visit a node, increment the number of the current level by 1. Since you won't visit it again, each tree node is counted only once.

Java语言: WidthOfBinaryTree

01 public int maxWidth(TreeNode root)
02 {
03     if(root==null)
04         return 0;
05     //define an array to record the number of nodes in each level
06     //assume the max number of levels is 1000
07     int []levels=new int[1000];
08     int max=0;
09     maxWidthHelper(levels,0,root);
10     //iterate through the level array, find max
11     for(int i=0;i<1000;i++)
12     {
13         if(levels[i]>max)
14         {
15             max=levels[i];
16         }
17     }
18     return max;
19 }
20 
21 public void maxWidthHelper(int [] levels, int depth, TreeNode root)
22 {
23     if(root==null)    return;
24     //visit this node, increment the number of nodes in the current level
25     levels[depth]++;
26     //DFS on children of the next level
27     maxWidthHelper(levels, depth+1, root.left);      
28     maxWidthHelper(levels, depth+1, root.right);      
29 }

Make Changes

Given an infinite number of quarters (25 cents), dimes (10 cents), nickles (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

Solution: this question is similar to Combination Sum, while is simpler. We do not need to output the combination, but just give the number of ways. Solve it recursively.
Ways = representing n cents by using 0 quarter,
          + representing n cents by using 1 quarter,
          + representing n cents by using 2 quarters
             ...
          + representing n cents by using many quarters

Then for each case, the formula can be expanded as
            representing 100 cents by using 0 dime
          + representing 100 cents by using 1 dime
              ...
          + representing 75 cents by using 0 dime
          + representing 75 cents by using 1 dime

Java语言: Coins

01 public int numOfWays(int sum)
02 {
03     int []coins={25,10,5,1};
04   
05     //start from quarters
06     return numOfWays(sum,coins,0);
07 }
08 
09 public int numOfWays(int sum, int [] coins, int start)
10 {
11 
12     if(sum<0)
13         return 0;
14   
15     //Base case: only pennies are used
16     if(start==coins.length-1)
17     {
18         return 1;
19     }
20   
21     int value=coins[start];
22     int ways=0;
23   
24     //use the coin at coins[start] 0, 1, 2 or many times
25     while(sum>=0)
26     {              
27         ways+=numOfWays(sum,coins,start+1);
28         sum-=value;
29     }
30     return ways;
31 }

Combination Sum II

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

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6] 

Solution: slightly modified from Combination Sum.

Java语言: CombinationSumII

01 public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(num.length==0)
04         return results;
05     Arrays.sort(num);
06     ArrayList<Integer> temp=new ArrayList<Integer>();
07     doCombine(results, temp, num, target, 0);
08     return results;
09 }
10 
11 public void doCombine(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> temp, int [] num, int target, int start)
12 {
13     for(int i=start;i<num.length;i++)
14     {
15         if(target==num[i])
16         {
17             temp.add(num[i]);
18             ArrayList<Integer> out=new ArrayList<Integer>(temp);
19             if(!results.contains(out))
20                 results.add(out);
21           
22         }
23         else if(target>num[i])
24         {
25             temp.add(num[i]);
26             doCombine(results, temp, num, target-num[i], i+1);
27         }
28         else
29         {
30             return;
31         }
32       
33         int size=temp.size();
34         if(size>0)
35             temp.remove(size-1);
36     }
37 }

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.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

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

Hing: use recursion. Iterate through the sorted candidate array. Start from the first element of the array. Use a temp buffer to store the number you have picked. Each element can be picked multiple times. There are three situation. If the sum equals the target, then output this temp buffer. If the sum is less than target, continue the selection process from the next position. If it's already greater than the target, abort this temp buffer. An important thing is that, you never go back again to smaller values. As the above example, you start from [2], then [2, 2], and [2,2,2]. When you select [2, 2, 2, 2], you find it is already larger than 7, so just abort it. Then 2, 2, 3, which is an result. Then you find 2, 2, 6...and you just abort this selection, then starting [2, 3]..., [3], [3,3]....

01 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(candidates.length==0)
04         return results;
05     ArrayList<Integer> temp=new ArrayList<Integer>();
06     Arrays.sort(candidates);
07     doCombine(results, temp, candidates, 0, target);
08     return results;
09   
10 }
11 
12 public void doCombine(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> temp, int [] candidates, int start, int target)
13 {
14   //Iterate through each number. Start from the first number.
15   //Each number can be used multiple times, until we pick up the next number
16     for(int i=start;i<candidates.length;i++)
17     {
18       //Base case: target equals the current number, add it to the temp buffer, output it.
19         if(target-candidates[i]==0)
20         {
21             temp.add(candidates[i]);
22             ArrayList<Integer> out=new ArrayList<Integer>(temp);
23             results.add(out);
24           
25         }
26       //Target larger than the current number, then new target becomes target-candidates[i].
27       //Add candidates[i] to the temp buffer. Call the fuction itself recursively
28         else if(target-candidates[i]>0)
29         {
30               
31             temp.add(candidates[i]);
32             doCombine(results, temp, candidates, i, target-candidates[i]);
33         }
34 
35       //Target smaller than the current number. Such combination is not valid. Return.
36         else
37         {
38             return;
39         }
40        //Remove the last element of the temporary buffer
41         int size=temp.size();
42         if(size>0)
43             temp.remove(size-1);
44     }
45 }

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.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ â‰¤ a₂ â‰¤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

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

Solution:

01 public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
02     ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
03     if(candidates.length==0)
04         return results;
05     ArrayList<Integer> temp=new ArrayList<Integer>();
06     Arrays.sort(candidates);
07     doCombine(results, temp, candidates, 0, target);
08     return results;
09   
10 }
11 
12 public void doCombine(ArrayList<ArrayList<Integer>> results, ArrayList<Integer> temp, int [] candidates, int start, int target)
13 {
14   //Iterate through each number. Start from the first number.
15   //Each number can be used multiple times, until we pick up the next number
16     for(int i=start;i<candidates.length;i++)
17     {
18       //Base case: target equals the current number, add it to the temp buffer, output it.
19         if(target-candidates[i]==0)
20         {
21             temp.add(candidates[i]);
22             ArrayList<Integer> out=new ArrayList<Integer>(temp);
23             results.add(out);
24           
25         }
26       //Target larger than the current number, then new target becomes target-candidates[i].
27       //Add candidates[i] to the temp buffer. Call the fuction itself recursively
28         else if(target-candidates[i]>0)
29         {
30               
31             temp.add(candidates[i]);
32             doCombine(results, temp, candidates, i, target-candidates[i]);
33         }
34 
35       //Target smaller than the current number. Such combination is not valid. Return.
36         else
37         {
38             return;
39         }
40        //Remove the last element of the temporary buffer
41         int size=temp.size();
42         if(size>0)
43             temp.remove(size-1);
44     }
45 }