使用不知道二叉查找树高度的顺序遍历的第k大元素

Question

我们可以在不知道二叉查找树的高度的情况下使用顺序遍历找到第k个最大的元素吗？或者有没有一种方法可以让我们创建一个新的遍历模式，比如“右根向左”

Answer 1

你说的是简单的二叉树还是像AVL树这样的树？

如果我理解正确，你根本不需要知道高度...顺序遍历-右根左-应该从最高值到最低值。

每次输入函数时，可以增加一个静态变量（或向函数发送另一个参数），直到达到K。

您还可以维护一个度树，并直接知道在哪里通过该树。

Answer 2

这个怎么样：

• 设x为对应于树的最小元素的节点（例如，x=T.root；而（x-

在BST上实现前置和后续方法并不困难，而且当节点具有指向父节点的额外指针时，实现起来也很容易。

Answer 3

在不知道二叉搜索树的高度的情况下，我们是否可以通过按序遍历找到第k个最大的元素<是的，我们可以我们可以使用一些额外的空间来完成。我们不一定需要做右根左来找出kth最大的元素（尽管这样做可以避免使用额外的空间）。

有几种方法。

最基本的是有一个队列。

无论何时，只要按顺序遍历，请继续在队列中插入值。不用说，由于它是二叉查找树，队列将被排序。因此，kth最大的元素位于queue.size（）-1-k索引处。（假设第0个largrst是最大元素，第一个最大的是第二个最大元素，以此类推）这种方法需要额外的空间，而不管k

为了优化使用的空间，我们可以使用关于k
的信息。注意，我们只需要（queue.size（）-1-k）第个索引处的元素。因此，我们可以有一个大小为（k1）的队列。在插入元素之前，我们将检查队列是否有超过k个元素，如果有，我们将从前面删除一个元素，因为我们不需要它
遍历完成后，kth最大的元素将位于队列的前面。

以下是这两种方法的java实现：

import java.util.LinkedList;
import java.util.Queue;

class Node {
    int data;
    Node left;
    Node right;

    static Queue<Integer> efficient = new LinkedList<>();
    static Queue<Integer> complete = new LinkedList<>();

    Node(int n) {
        this.data = n;
        this.left = null;
        this.right = null;
    }

    public static void inorder(Node node, int k) {
        if (node == null) {
            return;
        }
        inorder(node.left, k);
        if (efficient.size() > k) {
            efficient.poll();
        }
        efficient.add(node.data);
        complete.add(node.data);
        System.out.println(efficient.toString());
        inorder(node.right, k);
    }

    public static void main(String[] args) {
        Node root = new Node(7);
        root.left = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.left.right.right = new Node(6);
        root.right = new Node(9);
        int k = 2;
        inorder(root, k);
        System.out.println("Efficient queue size : " + efficient.size() + " " + efficient.peek());
        System.out.println("Full queue size : " + complete.size() + " " + complete.toArray()[complete.size() - 1 - k]);

    }

}

运行此命令，您将了解队列的增长效率请注意，此处，k应小于树中的节点数。如果不是，那么答案将是最小的元素。

其他方法使用堆实现更通用的解决方案。在这种情况下，树不需要是二进制搜索树。