[CS 61B Spring 2015] Discussion 9

Discussion 9的内容是Binary Search Tree。

1. import java.util.Arrays;
   
2. 
   
3. public class BSTNode {
   
4.         public BSTNode left, right;
   
5.         public int value;
   
6. 
   
7.         public BSTNode(int n) {
   
8.                 value = n;
   
9.         }
   
10. 
    
11.         public static int[] slice(int[] arr, int begin, int end) {
    
12.                 if (begin < 0 || begin > arr.length || end < 0 || end > arr.length
    
13.                         || begin >= end) {
    
14.                         return null;
    
15.                 }
    
16.                 int[] result = new int[end - begin];
    
17.                 for (int i = 0, j = 0; i < arr.length; i++) {
    
18.                         if (i >= begin && i < end) {
    
19.                                 result[j] = arr[i];
    
20.                                 j++;
    
21.                         }
    
22.                 }
    
23.                 return result;
    
24.         }
    
25. 
    
26.         public static BSTNode makeBST(int[] nums) {
    
27.                 if (nums.length == 0) {
    
28.                         return null;
    
29.                 } else if (nums.length == 1) {
    
30.                         return new BSTNode(nums[0]);
    
31.                 }
    
32.                 int mid = nums.length / 2;
    
33.                 BSTNode result = new BSTNode(nums[mid]);
    
34.                 result.left = makeBST(slice(nums, 0, mid));
    
35.                 result.right = makeBST(slice(nums, mid + 1, nums.length));
    
36.                 return result;
    
37.         }
    
38. 
    
39.         /* Returns the BSTNode that is the shortest common ancestor of n1 and n2. */
    
40.         public static BSTNode commonAncestor(BSTNode root, int n1, int n2) {
    
41.                 if (n1 > n2) {
    
42.                         return null;
    
43.                 }
    
44.                 if (n1 <= root.value && n2 >= root.value) {
    
45.                         return root;
    
46.                 }
    
47.                 if (n1 > root.value) {
    
48.                         return commonAncestor(root.right, n1, n2);
    
49.                 }
    
50.                 if (n2 < root.value) {
    
51.                         return commonAncestor(root.left, n1, n2);
    
52.                 }
    
53.                 return null;
    
54.         }
    
55. }

复制代码