二叉搜索树的第 k 大的节点

Question

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

递归1

中序遍历所有值，得到所有数组，然后取倒数第k个

function kthLargest(root, k) {
    let res = [];
    const inorder = (root) => {
        if (root === null) {
            return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res[res.length - k];
}

递归2

中序遍历倒序，找到最右边的节点，然后回溯

function kthLargest1(root, k) {
    let res = null
    const dfs = (root) => {
        if (!root) {
            return
        }
        dfs(root.right)
        if (k === 0) {
            return
        }
        if (--k === 0) {
            res = root.val
        }
        dfs(root.left)
    }
    dfs(root)

    return res
}