二叉搜索树的第 k 大的节点 | HZFE - 剑指前端 Offer

[utterances-bot]

二叉搜索树的第 k 大的节点 | HZFE - 剑指前端 Offer

题目描述

https://febook.hzfe.org/awesome-interview/book3/algorithm-binary-tree-k

[WebChn]

解法1 加一个return 是不是可以减少一些执行
const kthLargest = (root, k) => {
let res = null; // 初始化返回值
// 因为需要倒序第 k 个，所以处理是右节点，根节点，然后左节点
const dfs = (root) => {
if (!root) return; // 如果当前节点为 null，本轮处理结束
dfs(root.right); // 开始处理右节点
if (k === 0) return; // k 值 为 0，代表已经处理的节点超过目标节点，本轮处理结束
if (--k === 0) {
// 当 k 值 减 1 为 0，表示已经到了我们想要的 k 大 节点，保存当前值
res = root.val;
return // 这里已经拿到第 k 大的值了 后续的dfs(root.left); 不用再执行了
}
dfs(root.left); // 处理左节点
};
dfs(root); // 从初始化节点开始处理
return res;
};