题目描述

  1. 剑指 Offer 54. 二叉搜索树的第k大节点
  2. 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
  6. 示例 1:
  8. 输入: root = [3,1,4,null,2], k = 1
  9.    3
  10.   / \
  11.  1   4
  12.   \
  13.    2
  14. 输出: 4
  15. 示例 2:
  17. 输入: root = [5,3,6,2,4,null,null,1], k = 3
  18.        5
  19.       / \
  20.      3   6
  21.     / \
  22.    2   4
  23.   /
  24.  1
  25. 输出: 4
  28. 限制：
  30. 1 ≤ k ≤ 二叉搜索树元素个数

https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

解题思路

思路 这就是考察二叉树的遍历嘛，那就是中序遍历好了
中序遍历到第K个结果输出即可
只不过要求第K大，所以需要先右后中再左
有没有更快的方法？
要是假设二插搜索树是完全二叉树或者什么特殊的性质，就可以有更快的方法

代码实现

  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 i=0;
  13.     int tmp_n;
  14.     void visitTree(TreeNode* root,int k){
  15.         if(root->right!=nullptr) visitTree(root->right,k);
  16.         i++; 
  17.         if(i==k) tmp_n = root->val; 
  18.         if(root->left!=nullptr) visitTree(root->left,k);
  20.     }
  21.     int kthLargest(TreeNode* root, int k) {
  22.         visitTree(root,k);
  23.         return tmp_n;
  24.     }
  25. };

时间复杂度分析

二叉树遍历的时间，其实可以优化一下，就是不用全部搜索一遍

[

](https://www.zhihu.com/question/38842804/answer/78413820)