이진 검색 트리에서 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

음, 자바는 값 언어에 의한 패스 그래서 그것을 호출 된 메소드의 count의 값을 변경하지 않는 한 메서드 호출에 count의 값을 변경한다. k입니다 5 및 count는 4 때 재귀 동안 어떤 시점에서 가정하자

, 당신은 요구하고있다 :

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

이 호출이 count이 5에 전달 증가, 일부 sum를 반환한다고 가정하자.

이제 다시 findSumRec(root.left, 5, 4)를 호출 한 방법이고, 당신이 확인 : 최근에 반환 재귀 호출은 당신이 수행해야 의미 5까지 count을 가져왔다하더라도

 if(4 >= 5) 
      return sum; 

는 발신자가 여전히 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); 
} 

포인트는 모든 재귀 방법은 count 변수의 값을 수정과 공유 할 수 있어야합니다 findSumRec 호출한다는 것입니다. count이 메소드에 전달 된 기본 변수 인 경우 각 메소드가 해당 변수의 다른 사본을 가져 오기 때문에 불가능합니다.

배열을 사용하는 것이 하나의 옵션입니다. 또 다른 옵션은 인수로 전달하는 대신 메소드를 포함하는 클래스의 멤버 변수를 사용하는 것입니다. 이 방법은 여전히 ​​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); 
    } 
} 

방법에 내 코드 논리를 참조 자바

내 코드입니다.

희망이 도움이됩니다.