二叉搜索树中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。

希望这会有所帮助！