java - 在二叉搜索树中查找 K 个最大元素

Question

我试图找到 BST 中的 K 个最大元素，但我的代码流程没有正确发生。例如，考虑如下 BST

             9
           /   \
          7     12
         /  \  /   \
        6  10  11  16

我的代码流按照 16 --> 12 --> 9 的顺序发生，尽管我试图让它为 16 --> 12 --> 11。

代码如下

public class FindKLargestElements {


private static int n =0;

public static int[] findLarge(Node node, int large[], int k) {

    if (node == null) return large;

    if (k == 0) return large;

    findLarge(node.getRightNode(), large, k);

    if (k >0) {
        large[n] = node.getValue();
        k = k -1;
        n = n +1;
        return large;

    }

    findLarge(node.getLeftNode(), large, k);

    return large;

}

}

我现在已经解决了这个问题。这是最终的代码。

这就是我所做的

1. 从 if k > 0 block 中删除了 return 语句

2. 将基元 k 更改为类级别而不是递归方法级别，因为更新后的 k 会丢失。

   public class FindKLargestElements {
   
   
   private static int n =0;
   private static int k =3;
   
   public static int[] findLarge(Node node, int large[]) {
   
       if (node == null) return large;
   
       if (k == 0) return large;
   
       findLarge(node.getRightNode(), large);
   
       if (k >0) {
           large[n] = node.getValue();
           k = k -1;
           n = n +1;
   
       }
   
       findLarge(node.getLeftNode(), large);
   
       return large;
   
   }
   

   }

Answer 1

请尝试以下程序

public class FindKLargestElements {

private static int n =0;
private static int large[];

public static void findLarge(Node node, int k) {

    if (node == null) return;
    if (k == 0) return;

    findLarge(node.getRightNode(), k);

    if (k >0) {
        large[n] = node.getValue();
        k = k-1;
        n = n+1;

    }

    findLarge(node.getLeftNode(), k);

}

}