剑指offer62:二插搜索树的第k个节点

题目描述:

给定一颗二叉搜索树,请找出其中的第k大的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个结点的值为4。

中序遍历

 /*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNodeHelper(TreeNode* pRoot, int k, int& count) {
if (pRoot == nullptr) {
return nullptr;
}
TreeNode* node = KthNodeHelper(pRoot->left, k, count);
if(node) return node;
count++;
if (k == count) {
return pRoot;
}
node = KthNodeHelper(pRoot->right, k, count);
if(node) return node;
return nullptr;
}
TreeNode* KthNode(TreeNode* pRoot, int k) {
if(k<=) return nullptr;
int count = ;
return KthNodeHelper(pRoot, k, count);
}
};
上一篇:5分钟创建一个Microsoft Teams简易机器人


下一篇:Codeforces 908B New Year and Buggy Bot 题解