java - 在二叉搜索树中打印最大的 n 个值

Question

我正在尝试创建一种方法来打印出二叉搜索树中最大的 n 个值。我正在考虑改变逆序打印方法来实现这一点。

倒序打印方法:

public static void reverseOrderPrint(TreeNode node) {
    if (node == null) return;
    reverseOrderPrint(node.right);
    System.out.println(node.data);
    reverseOrderPrint(node.right);
}

我想把上面的方法修改成这样来达到我的目的

// print BST reverse Order
public static void reverseOrder(TreeNode node, int n) {
    if (sizeOfBinaryTree(node) < n) {
        System.out.print("n is bigger than tree");
        return;
    }
    if (node == null) return;
    reverseOrder(node.right);
    System.out.print(node.data);
    reverseOrder(node.left);
}

我曾考虑过将逆序元素存储在数组中，然后返回前 n 个值，但这将具有 O(n) 的性能并且需要额外的内存。如何在不需要额外内存的情况下递归执行相同的任务？这也有可能在 O(log n) 中完成这个问题吗？还是必须是 O(n)？

Answer 1

将您的方法更新为以下内容，它将打印最大的 n 个值。您可以将 n bigger than tree 的测试移到方法之外。初始调用 i=0;

// print BST reverse Order
public static void reverseOrder(TreeNode node, int n,int i) {
    if (node == null) return;
        reverseOrder(node.right,n,i);
        if(++i<n) System.out.print(node.data);
        reverseOrder(node.left,n,i);
    }
}