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

🟢   🔖  树 深度优先搜索 二叉搜索树 二叉树  🔗 LeetCode

题目

某公司组织架构以二叉搜索树形式记录，节点值为处于该职位的员工编号。请返回第 cnt 大的员工编号。

示例 1：

输入：root = [7, 3, 9, 1, 5], cnt = 2

输出：7

    7
   / \
  3   9
 / \
1   5

示例 2：

输入: root = [10, 5, 15, 2, 7, null, 20, 1, null, 6, 8], cnt = 4

输出: 8

      10
     / \
    5   15
   / \    \
  2   7    20
 /   / \
1   6   8

提示：

1 ≤ cnt ≤ 二叉搜索树元素个数

解题思路

这道题很像 230. 二叉搜索树中第 K 小的元素，只不过 230 题求第 k 小的值，这里求第 k 大的值。

本题也可以利用 BST 的中序遍历计算第 k 大的元素。只不过常规的中序遍历得到的顺序是从小到大的，而我们想得到从大到小的顺序。

只要把中序遍历框架反过来，先递归遍历右子树，再递归遍历左子树，即可获得降序结果。

代码

/**
 * @param {TreeNode} root
 * @param {number} cnt
 * @return {number}
 */
var findTargetNode = function (root, cnt) {
	let i = 0;
	let res;
	const traverse = (root) => {
		if (!root) return null;
		traverse(root.right);
		i++;
		if (i == cnt) {
			res = root.val;
			return;
		}
		traverse(root.left);
	};
	traverse(root);
	return res;
};