54. 二叉搜索树的第k大节点
1. 描述
给定一棵二叉搜索树，请找出其中第k大的节点。
2. 例子
示例 1:
输入: root = [3,1,4,null,2], k = 1
输出: 4
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
输出: 4
3. 限制
- 1 ≤ k ≤ 二叉搜索树元素个数
4. 题解
n 是 i_root 中的节点个数
时间复杂度: O(n)
空间复杂度: O(n)
class Solution
{
private:
int kthNode;
void iterateTree(TreeNode *i_root, int &m_k)
{
if(i_root->right) iterateTree(i_root->right, m_k);
m_k--;
if(m_k == 0)
{
kthNode = i_root->val;
return ;
}
if(i_root->left) iterateTree(i_root->left, m_k);
}
public:
// int kthLargest(TreeNode* root, int k)
int kthLargest(TreeNode *i_root, int k)
{
iterateTree(i_root, k);
return kthNode;
}
};