跳转至

剑指 Offer 54. 二叉搜索树的第k大节点

题目描述

原题

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

示例 1:

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

示例 2:

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

限制：

1 ≤ k ≤ 二叉搜索树元素个数

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int kthLargest(TreeNode root, int k) {
        //二叉搜索树的中序遍历 是有序的
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            if(node.right!=null){
                root = node.right;
            }
        }
        //正序 所以list.size()-k
        return list.get(list.size()-k);
    }
}