【剑指offer:二叉搜索树的第k大节点】

题目描述:给定一棵二叉搜索树,请找出其中第 k 大的节点。

这题LeetCode 230.二叉搜索树中第 K 小的元素差不多。只不过按照题目要求,这题是要按照从大到小的逆序顺序,访问二叉搜索树的元素。所以要改造下中序遍历的顺序:右节点 => 当前节点 => 左节点。

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
// 原文地址:https://xxoo521.com/2020-03-15-bst-k-number/
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let step = 0;
    let res = null;
    inorder(root);
    return res;

    function inorder(node) {
        if (!node) return;

        inorder(node.right);
        if (++step === k) {
            res = node;
        }
        inorder(node.left);
    }
};

更多资料

整理不易,若对您有帮助,请给个「关注+点赞」,您的支持是我更新的动力 👇

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×