剑指offer 面试题54. 二叉搜索树的第k大节点（易）

考查应聘者的知识迁移能力。考查应聘者对二叉搜索树和中序遍历的特点的理解。如果应聘者理解二叉搜索树的中序遍历序列是递增的，那么他/她很容易就能找出第k大的节点。

Question

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

测试用例

功能测试（各种形态不同的二叉搜索树）。 边界值测试（输入k为0、1、二叉搜索树的节点数、二叉搜索树的节点数加1）。 特殊输入测试（指向二叉搜索树根节点的指针为 nullptr 指针）。

本题考点

考查应聘者的知识迁移能力。面试官期待应聘者能够运用中序遍历算法来解决这道面试题。 考查应聘者对二叉搜索树和中序遍历的特点的理解。如果应聘者理解二叉搜索树的中序遍历序列是递增的，那么他/她很容易就能找出第k大的节点。

Intuition

对输入的树，进行中序遍历（右根左）操作，得到递减序列。然后顺序输出第 \(k\) 大的值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def inOrder(self, root):
        if not root:  return []
        res = [root.val]
        left_tree = self.inOrder(root.left)
        right_tree = self.inOrder(root.right)
        return right_tree + res + left_tree


    def kthLargest(self, root: TreeNode, k: int) -> int:
        # 中序遍历
        if not root:  return None
        res = self.inOrder(root)
        if k > len(res): return None

        # 输出第K个结果
        return res[k-1]