二叉搜索树的第 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; };