剑指Offer 54. 二叉搜索树的第 k 大节点

[Douc1998]

题目

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

示例

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4

解

考点：中序遍历，由于是求第 k 大的节点，因此应该先遍历右子树，然后中间节点，最后左子树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthLargest = function(root, k) {
    let res = -1;
    // 中序遍历，但是是从右子树先开始，因为要求第 k 大的值
    var dfs = function(root){
        if(root === null) return;
        dfs(root.right);
        // 提前返回
        if(k === 0) return;
        if(--k === 0){
            res = root.val;
        }
        dfs(root.left);
    }
    dfs(root);
    return res;
};