二叉搜索樹中K個最小元素的總和

Question

任何人都可以請建議，下面的代碼找到BST中k個最小元素的總和有什麼問題？它返回樹中所有節點的總和。

public int findSum(Node root, int k){ 
      int count = 0; 
      return findSumRec(root, k, count); 
     } 

     private int findSumRec(Node root, int k, int count) { 

      if(root == null) 
       return 0; 
      if(count > k) 
       return 0; 

      int sum = findSumRec(root.left, k, count); 
      if(count >= k) 
       return sum; 

      sum += root.data; 
      count++; 

      if(count >= k) 
       return sum; 
      return sum + findSumRec(root.right, k, count); 
      } 

Answer 1

那麼，Java是按值傳遞的語言，所以改變一個方法調用的count值不會改變調用它的方法count值。

假設在遞歸過程中的某個時刻，當k是5和count是4，你在呼喚：

 int sum = findSumRec(root.left, 5, 4); 

假設這個調用增加了count傳遞給它5，並返回一些sum。

現在你又回到那個叫findSumRec(root.left, 5, 4)的方法和你檢查：

 if(4 >= 5) 
      return sum; 

即使最近返回遞歸調用帶來count高達5，這意味着你應該做的，調用者仍然認爲count作爲4（因爲它不是相同的count變量），因此樹的遍歷將繼續，直到您訪問樹的所有節點並將所有節點相加。

您必須使用一些可變實例來修改count。

例如，可以使用具有單個元素的數組：

public int findSum(Node root, int k){ 
    int[] count = {0}; 
    return findSumRec(root, k, count); 
} 

和

private int findSumRec(Node root, int k, int[] count) { 
    ... 
    change each count to count[0] 
    ... 
} 

編輯：我剛剛與我的建議的校正測試你的代碼，它的工作原理。

public int findSum(Node root, int k) { 
    int[] count = {0}; 
    return findSumRec(root, k, count); 
} 

private int findSumRec(Node root, int k, int[] count) { 

    if(root == null) 
     return 0; 
    if(count[0] > k) 
     return 0; 

    int sum = findSumRec(root.left, k, count); 
    if(count[0] >= k) 
     return sum; 

    sum += root.val; 
    count[0]++; 

    if(count[0] >= k) 
     return sum; 
    return sum + findSumRec(root.right, k, count); 
} 

的一點是，所有的遞歸方法調用findSumRec必須共享count變量的值，並能夠改變它。當count是一個傳遞給方法的原始變量時，這是不可能的，因爲每個方法獲得該變量的不同副本。

使用數組是一種選擇。另一個選擇是使用包含您的方法的類的成員變量，而不是將其作爲參數傳遞。這樣它仍然可以是int。

Answer 2

我認爲你正在尋找這樣的事情，這是我在Java

import java.io.*; 

public class Main { 

    public static class Node { 
    int val; 
    Node left; 
    Node right; 
    public Node(int data) { 
     this.val = data; 
     this.left = null; 
     this.right = null; 
    } 
    } 

    public static int sum_ans = 0; 

    public static int count_k_smallest_sum(Node root, int count, int k) 
    { 
    if(count>=k) 
    { 
     return 100005; 
    } 
    if(root.left == null && root.right == null) 
    { 
     sum_ans += root.val; 
     return count+1; 
    } 
    int cnt = count; 
    if(root.left != null) 
    { 
     cnt = count_k_smallest_sum(root.left, cnt, k); 
    } 
    if(cnt >= k) 
    { 
     return 100005; 
    } 
    sum_ans += root.val; 
    cnt++; 

    if(cnt >= k) 
    { 
     return 100005; 
    } 

    if(root.right != null) 
    { 
     cnt = count_k_smallest_sum(root.right, cnt, k); 
    } 

    return cnt; 
    } 

    public static void main(String args[]) throws Exception { 
    Node root = new Node(10); 
    Node left1 = new Node(5); 
    Node right1 = new Node(11); 
    Node left2 = new Node(3); 
    Node right2 =new Node(12); 
    Node left3 = new Node(2); 
    Node right3 = new Node(7); 
    Node right4 = new Node(4); 
    root.left = left1; 
    root.right = right1; 
    right1.right = right2; 
    left1.left = left2; 
    left1.right = right3; 
    left2.left = left3; 
    left2.right = right4; 
    int cnt = count_k_smallest_sum(root, 0, 3); 
    System.out.println(sum_ans); 
    } 
} 

看到我的方法的代碼邏輯代碼 - count_k_smallest_sum。

希望這會有所幫助！