Summe von K kleinsten Elementen in der binären Suche Baum

Question

Könnte jemand bitte vorschlagen, was ist falsch mit diesem unter Code zum Finden der Summe von k kleinsten Elemente in einem BST? Es gibt die Summe für alle Knoten im Baum zurück.

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

Nun, Java ist ein Pass von Wert Sprache, so dass der Wert count in einem Methodenaufruf ändert nicht den Wert von count des Verfahrens ändern, die sie aufgerufen.

Es sei an einem gewissen Punkt während der Rekursion, wenn k ist 5 und count ist 4, die Sie anrufen:

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

Nehmen wir an, dieser Aufruf die count, um es zu 5 weitergegeben erhöht und gibt einige sum.

Jetzt sind Sie zurück auf die Methode, die findSumRec(root.left, 5, 4) genannt und Sie überprüfen:

 if(4 >= 5) 
      return sum; 

Obwohl die kürzlich zurück rekursiven Aufruf count bis zu 5 gebracht, was bedeutet, dass Sie getan werden sollte, noch der Anrufer sieht count als 4 (da es nicht die gleiche count Variable ist), und daher wird die Traversierung des Baumes fortgesetzt, bis Sie alle Knoten des Baums besuchen und alle von ihnen summieren.

Sie müssen eine veränderbare Instanz verwenden, um die count zu ändern.

Zum Beispiel können Sie einen Array verwenden, um ein einzelnes Element mit:

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

und

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

EDIT: Ich habe Ihren Code mit mir vorgeschlagenen Korrektur nur getestet, und es funktioniert.

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

Der Punkt ist, dass alle die rekursive Methode findSumRec aufruft, muss den Wert der count Variable teilen und in der Lage sein, es zu ändern. Dies ist nicht möglich, wenn count eine primitive Variable ist, die an die Methode übergeben wird, da jede Methode eine andere Kopie dieser Variable erhält.

Die Verwendung eines Arrays ist eine Option. Eine andere Option besteht darin, eine Membervariable der Klasse zu verwenden, die Ihre Methoden enthält, anstatt sie als Argument zu übergeben. So kann es immer noch int sein.

Answer 2

Ich glaube, Sie sind für so etwas suchen, ist hier mein Code in 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); 
    } 
} 

meinen Code-Logik in der Methode See - count_k_smallest_sum.

Hoffe, das hilft!