Once everything hit the base case now all the results just multiply to give us our result of 120
Binary tree data structure
This class we work with the simplest type of trees called binary trees.
Each node has a left node and a right node, they both don't have to be filled out but there never can be more of these.
A tree is a type of recursive data structure, that means that even the nodes are trees themselves, so it's right to think about each tree being made up of a left subtree and right subtree.
Since it is a recursive data structure, trees are great for recursive algorithms and trying to do these problems iteratively will be far more complex. This means your code for doing stuff like this will often be short, but tricky to figure out.
It gets better with practice :)
Full binary tree (10 minutes)
Given a Tree, return a list of all the node values that are single leaves. (single meaning they are the only leaf corresponding to a parent node, Right or Left, but not both)
import java.util.ArrayList;
import java.util.List;
publicclassTree{
int value;
Tree left;
Tree right;
}
publicstatic List<Integer> findSingleLeaves(Tree t){
List singleLeaves = new ArrayList();
return singleLeaves
}
Sorting
Simply put, sorting algorithims are ones designed to sort a list of items in order
Given two strings s and t , write a function to determine if t is an anagram of s. Hint: Try to see how using Arrays.sort() could help you solve this faster
Geoff has given Chuchu an allowance for being a good boi. Chuchu now wants to use the money he has saved up to buy as many chew toys as he can. as he chew-chews through a lot of them. You are given Chuchu's allowance and an array of the toys and their prices (you can assume that every item in the store's inventory has its own price int in the array, so duplicates exist). Return the max number of toys chuchu could buy.
Solve this with sorting!
3 bones ($5 each), 1 rope ($2 each), 2 plushies($3 each) would look like
[5, 5, 5, 2, 3, 3]
If chuchu had 9 dollars, the most he could get in this example would be 1 rope, and two plushies, return 3
(no seriously, attempt the problems with your groupmates first!)
1)
import java.util.ArrayList;
import java.util.List;
publicclassTree{
int value;
Tree left;
Tree right;
}
publicstatic List<Integer> findSingleLeaves(Tree t){
List singleLeaves = new ArrayList();
singleHelper(t, singleLeaves);
return singleLeaves;
}
publicstaticvoidsingleHelper(Tree t, List list){
if (t == null) {
return;
}
if (t.left == null ^ t.right == null) {
list.add(t);
}
singleHelper(t.left, list);
singleHelper(t.right, list);
}
2)
import java.util.Arrays;
publicbooleanisAnagram(String s, String t){
if (s.length() != t.length()) {
returnfalse;
}
var arrS = s.toCharArray();
var arrT = s.toCharArray();
Arrays.sort(arrS);
Arrays.sort(arrT);
return Arrays.equals(arrS, arrT);
}
System.out.println(isAnagram("harsh", "hrsah"));
3)
import java.util.Arrays;
// O(n) loop with O(nlogn) sort over naive O(n^2)intmaxToys(int allowance, int[] toyInventory){
Arrays.sort(toyInventory);
int toyCount = 0;
while (allowance > 0) {
allowance -= toyInventory[toyCount];
toyCount++;
}
return toyCount - 1;
// toyCount is the number of toys till we run out of money// so -1 is the number of toys we can get with some money left
}
int[] toys = {5, 5, 5, 2, 3, 3};
assertmaxToys(9, toys)== 3;