<![CDATA[
CSE143 Key to Final, Spring 2024 handout #26
1. Preorder traversal 3, 5, 9, 6, 0, 2, 7, 8, 4, 1
Inorder traversal 3, 0, 6, 2, 9, 5, 4, 8, 7, 1
Postorder traversal 0, 2, 6, 9, 4, 8, 1, 7, 5, 3
2. +------------+
| Luke |
+------------+
/ \
/ \
+------------+ +------------+
| Kylo | | Poe |
+------------+ +------------+
/ / \
/ / \
+------------+ +------------+ +------------+
| BB8 | | Maz | | Rey |
+------------+ +------------+ +------------+
\
\
+------------+
| Finn |
+------------+
3. Two-Dimensional Array Contents of Set Returned
------------------------------------------------------------------
[[1, 2], [3, 4]] [1, 2, 13, 14]
[[7], [], [8, 8, 9, 10]] [7, 28, 29, 30]
[[3, 14], [5, 13, 4], [4, 3, 1]] [3, 14, 15, 21, 23, 24]
4. One possible solution appears below.
public void recordTrip(Map<String, Set<String>> trips,
String person, String place) {
if (!trips.containsKey(person)) {
trips.put(person, new TreeSet<>());
}
trips.get(person).add(place);
}
5. Binary Trees, 10 points. One possible solution appears below.
public void printLeaves() {
if (overallRoot == null) {
System.out.println("no leaves");
} else {
System.out.print("leaves:");
printLeaves(overallRoot);
System.out.println();
}
}
private void printLeaves(IntTreeNode root) {
if (root != null) {
if (root.left == null && root.right == null)
System.out.print(" " + root.data);
} else {
printLeaves(root.right);
printLeaves(root.left);
}
}
}
6. One possible solution appears below.
public Set<Point> removePoints(Map<Integer, List<Point>> points, int n) {
Set<Point> removed = new HashSet<>();
if (points.containsKey(n)) {
Iterator<Point> itr = points.get(n).iterator();
while (itr.hasNext()) {
Point p = itr.next();
if (p.getX() < p.getY()) {
itr.remove();
removed.add(p);
}
}
}
return removed;
}
7. One possible solution appears below.
public class ItemOrder implements Comparable<ItemOrder> {
private String item;
private int quantity;
private int pricePer;
private String note;
public ItemOrder(String item, int quantity, int pricePer) {
this(item, null, quantity, pricePer);
}
public ItemOrder(String item, String note, int quantity,
int pricePer) {
this.item = item;
this.note = note;
this.quantity = quantity;
this.pricePer = pricePer;
}
public String getItem() {
return item;
}
public int getPrice() {
return quantity * pricePer;
}
public String toString() {
String text = "item #" + item;
if (note != null) {
text += " (" + note + ")";
}
text = text + ": " + quantity + "@" + moneyString(pricePer) +
" = " + moneyString(getPrice());
return text;
}
private String moneyString(int cents) {
return "$" + cents / 100 + "." + cents % 100 / 10 + cents % 10;
}
public int compareTo(ItemOrder other) {
if (!item.equals(other.item)) {
return item.compareTo(other.item);
} else {
return other.getPrice() - getPrice();
}
}
}
8. One possible solution appears below.
public void makeFull() {
overallRoot = makeFull(overallRoot, 1);
}
private IntTreeNode makeFull(IntTreeNode root, int level) {
if (root != null) {
if (root.left == null && root.right != null) {
root = new IntTreeNode(-level, root, root.right);
root.left.right = null;
} else if (root.left != null && root.right == null) {
root = new IntTreeNode(-level, root.left, root);
root.right.left = null;
}
root.left = makeFull(root.left, level + 1);
root.right = makeFull(root.right, level + 1);
}
return root;
}
9. Two possible solutions appear below.
public void switchEvens(LinkedIntList other) {
if (front != null && other.front != null) {
ListNode temp = other.front;
other.front = front;
front = temp;
temp = front.next;
front.next = other.front.next;
other.front.next = temp;
ListNode curr1 = front.next;
ListNode curr2 = other.front.next;
while (curr1 != null && curr2 != null && curr1.next != null &&
curr2.next != null) {
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
temp = curr2.next.next;
curr2.next.next = curr1.next.next;
curr1.next.next = temp;
curr1 = curr1.next.next;
curr2 = curr2.next.next;
}
}
}
public void switchEvens(LinkedIntList other) {
if (front != null && other.front != null) {
ListNode temp = other.front;
other.front = front;
front = temp;
ListNode curr1 = front;
ListNode curr2 = other.front;
int count = 0;
while (curr1.next != null && curr2.next != null) {
count++;
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
curr1 = curr1.next;
curr2 = curr2.next;
}
if (count % 2 == 0) {
temp = curr2.next;
curr2.next = curr1.next;
curr1.next = temp;
}
}
}
]]>