描述

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

示例 1：

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

示例 2：

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

题解

本文解法基于此性质：二叉搜索树的中序遍历为 递增序列 。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8.  * };
  9.  */
  10. class Solution {
  11. public:
  12.     int kthLargest(TreeNode* root, int k) {
  13.         if(root == nullptr) return 0;
  14.         vector<int> arr;
  15.         inorder(root, arr);
  16.         return arr[--k];
  17.     }
  18.     void inorder(TreeNode* root, vector<int> &arr) {
  19.         if(root == nullptr) return;
  20.           // 注意，为了得到递减数列，先右 
  21.         inorder(root->right, arr);
  22.         arr.push_back(root->val);
  23.           // 再左
  24.         inorder(root->left, arr);
  25.     }
  26. };