二叉查找树中第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;
}

评论

暂无评论