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

题目

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

难度：🌟🌟

示例 1:

输入: root = [3,1,4,null,2], k = 1

输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3

输出: 4

限制：

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

题解

题目要求找到二叉搜索树的第K大的节点，我们可以利用二叉搜索树结构，即右子树比左子树大的特性，从右子树开始遍历，每遍历一个节点就对 k 减1，当 k 等于0时，此时的节点即为第 K 大的节点。

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargest(root *TreeNode, k int) int {
	var res *TreeNode
	var inorder func(node *TreeNode)
	inorder = func(node *TreeNode) {
		if node == nil {
			return
		}
		inorder(node.Right)
		k--
		if k == 0 {
			res = node
		}
		inorder(node.Left)
		return
	}
	inorder(root)
	return res.Val
}