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

Posted on | In
Words count in article: 147 | Reading time ≈ 1

题目

给定一棵二叉搜索树，请找出其中第 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 ≤ 二叉搜索树元素个数

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int kthLargest(TreeNode root, int k) {
        List<Integer> result = new ArrayList<>();
        travel(root, result);
        return result.get(result.size() - k);
    }

    private void travel(TreeNode root, List<Integer> result) {
        if (Objects.isNull(root)) {
            return;
        }

        travel(root.left, result);
        result.add(root.val);
        travel(root.right, result);
    }
0%