二叉查找树中第K大的节点
文章目录
中序遍历就是按照大小排序,在此基础上加一个计数器即可。
#include <iostream>
using namespace::std;
struct TreeNode {
int value;
TreeNode * left;
TreeNode * right;
TreeNode(int x): value(x), left(NULL), right(NULL) {}
};
void thirdNode(TreeNode * root, int &count, int target) {
if (count > target) return;
if (root->left == nullptr && root->right == nullptr) {
count++;
if (count == target) cout << root->value << endl;
return;
}
if (root->left) thirdNode(root->left, count, target);
count++;
if (count == target) cout << root->value << endl;
if (root->right) thirdNode(root->right, count, target);
}
int main(int argc, const char * argv[])
{
TreeNode * root = new TreeNode(4);
root->left = new TreeNode(2);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right = new TreeNode(7);
root->right->right = new TreeNode(9);
int count = 0;
thirdNode(root, count, 5); // 输出第 5 大的数
return 0;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论