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

给定一棵二叉搜索树，请找出其中第 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

限制：

• 1 ≤ k ≤ 二叉搜索树元素个数

---

### 解题思路 1.二叉搜索树的特点：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 2.使用右根左的中序遍历，就能得到递减的序列，因此遍历了第k次的当前节点所求的第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 node;
    if (!root) return node;
    // 中序遍历：右根左
    const dfs = (root) => {
        if (!root) return null;
        dfs(root.right);
        k--;
        if (!k) return (node = root.val);
        dfs(root.left);
    };
    dfs(root);
    return node;
};