バイナリ検索ツリーの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の値を変更しない1回のメソッド呼び出しでcountの値を変更すること、です。

kが5とcount4であるとき、あなたが呼び出している、再帰中のある時点で仮定します

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

は、この呼び出しは5に、渡されたcountを増加させ、いくつかのsumを返すと仮定します。

今、あなたは戻ってfindSumRec(root.left, 5, 4)と呼ばれ、あなたがチェックする方法にある。最近返さ再帰呼び出しは、呼び出し側がまだcountを見て、あなたが行われるべきことを意味する、5までcountを持っていても

 if(4 >= 5) 
      return sum; 

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] 
    ... 
} 

EDIT：

はたとえば、1つの要素を持つ配列を使用することができます。

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); 
} 

点は、すべての再帰的方法はcount変数の値を共有し、それを変更することができなければならないfindSumRecにコールすることです。 countがメソッドに渡されたプリミティブ変数である場合、各メソッドはその変数の異なるコピーを取得するため、これは不可能です。

アレイの使用は1つのオプションです。別のオプションは、引数として渡す代わりに、メソッドを含むクラスのメンバ変数を使用することです。このようにしても、それはまだintです。 count_k_smallest_sum -

Answer 2

は、私はあなたがこのような何かを探していると思いますが、ここで

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); 
    } 
} 

方法で私のコードのロジックを参照してくださいjavaの

で私のコードです。

希望すると便利です。