[数据结构与算法]【二叉树001】二叉搜索树中第K小的元素

二叉搜索树中第K小的元素 230

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

方法一:中序遍历

  public int kthSmallest(TreeNode root, int k) {
            Deque<TreeNode> deque = new ArrayDeque<>();
            while (root != null || !deque.isEmpty()) {
                while (root != null) {
                    deque.addLast(root);
                    root = root.left;
                }
                root = deque.pollLast();
                if (--k == 0) {
                    return root.val;
                }
                root = root.right;
            }
            return -1;
        }

方法二: 优先队列和栈

public int kthSmallest111(TreeNode root, int k) {
    PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
    Deque<TreeNode> deque = new ArrayDeque<>();
    deque.addLast(root);
    while (!deque.isEmpty()) {
        TreeNode treeNode = deque.pollFirst();
        if (queue.size() < k) {
            queue.add(treeNode.val);
        } else if (queue.peek() > treeNode.val) {
            queue.poll();
            queue.add(treeNode.val);
        }
        if (root.left != null) {
            deque.addLast(root.left);
        }
        if (root.right != null) {
            deque.addLast(root.right);
        }
    }
    return queue.peek();
}