[CS 61B Spring 2015] Discussion 10

Heaps & Hashing

1
(a) /
(b) Change the sign when putting in the heap. Change it again when returning value.

2
(a) Sometimes. When you have collisions by chance, you may still get the entry.
(b) Always. HashMap is based on hashing of keys, so changing its value won't affect retrieval.

3

1. public class SumPaths {
   
2.         public void printSumPaths(Node t, int k) {
   
3.                 if (t != null) {
   
4.                         sumPathsHelper(t, 0, "", k);
   
5.                 }
   
6.         }
   
7. 
   
8.         private void sumPathsHelper(Node n, int sum, String path, int k) {
   
9.                 sum += n.value;
   
10.                 path += n.value + " ";
    
11. 
    
12.                 if (n.left == null && n.right == null) {
    
13.                         if (sum == k) {
    
14.                                 System.out.println(path);
    
15.                         }
    
16.                         return;
    
17.                 }
    
18. 
    
19.                 if (n.left == null) {
    
20.                         sumPathsHelper(n.right, sum, path, k);
    
21.                 }
    
22. 
    
23.                 if (n.right == null) {
    
24.                         sumPathsHelper(n.left, sum, path, k);
    
25.                 }
    
26.         }
    
27. 
    
28.         private class Node {
    
29.                 Node left;
    
30.                 Node right;
    
31.                 int value;
    
32.         }
    
33. }

复制代码