jz54.二叉搜索树的第K大节点

题目描述

给定一棵二叉搜索树，请找出其中第k大的节点。

示例一：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例二：

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

题解

BFS + 排序

直观印象就是先将二叉树的节点遍历出来, 然后经过排序得出结果

public int kthLargest(TreeNode root, int k) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            res.add(temp.val);
            if (temp.left != null)
                queue.add(temp.left);
            if (temp.right != null)
                queue.add(temp.right);
        }

        Collections.sort(res);
        return res.get(res.size() - k);
    }

但是这样做的时间复杂度很差.

---

中序遍历(重要)

二叉搜索数的中序遍历为递增序列

只要得到二叉搜索树的中序遍历数组, 就直接免去了排序的过程, 大大加快程序执行速度.

public int kthLargest2(TreeNode root, int k) {
    List<Integer> res = new ArrayList<>();
    recur(res, root);
    return res.get(res.size() - k);
}

private void recur(List<Integer> res, TreeNode root) {
    if (root!=null){
        if (root.left!=null)
            recur(res, root.left);
        res.add(root.val);
        if (root.right!=null)
            recur(res, root.right);
    }
}