二叉搜索树的第k大元素

问题陈述

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

示例：

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

思路分析

由二叉搜索树的特点，知其中序遍历序列有序，为递增序列。这里可以仿中序弄一个倒中序（右根左）然后得到一个递减序列，第k个元素即为第k大节点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class KElementBST {
    public int getKthElement(TreeNode root,int k){
        List<Integer> list=new ArrayList<>();
        helper(root,list);
        return list.get(k);
    }
    //二叉搜索树中序有序，可倒中序遍历，正好得到降序序列
    public void helper(TreeNode root,List<Integer> list){
        if(root==null) return;
        if(root.right!=null){
            helper(root.right,list);
        }
        list.add(root.val);
        if(root.left!=null){
            helper(root.left,list);
        }
    }

    public static void main(String[] args) {
        KElementBST kElementBST=new KElementBST();
        TreeNode root=new TreeNode(5);
        root.left=new TreeNode(3);
        root.right=new TreeNode(6);
        System.out.println(kElementBST.getKthElement(root, 2));
    }
}