1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

// @Title: 二叉搜索树中第K小的元素 (Kth Smallest Element in a BST)
// @Author: 15816537946@163.com
// @Date: 2019-11-25 20:23:07
// @Runtime: 12 ms
// @Memory: 5.8 MB
/*
 * @lc app=leetcode.cn id=230 lang=golang
 *
 * [230] 二叉搜索树中第K小的元素
 *
 * https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/description/
 *
 * algorithms
 * Medium (65.92%)
 * Likes:    92
 * Dislikes: 0
 * Total Accepted:    19.7K
 * Total Submissions: 30K
 * Testcase Example:  '[3,1,4,null,2]\n1'
 *
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 *
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 * ⁠  3
 * ⁠ / \
 * ⁠1   4
 * ⁠ \
 * 2
 * 输出: 1
 *
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 * ⁠      5
 * ⁠     / \
 * ⁠    3   6
 * ⁠   / \
 * ⁠  2   4
 * ⁠ /
 * ⁠1
 * 输出: 3
 *
 * 进阶：
 * 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
 *
 */
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

 /*
func kthSmallest(root *TreeNode, k int) int {
	var kv int
	var findKth func(r *TreeNode)
	findKth = func(r *TreeNode) {
		if r == nil || k == 0 {
			return
		}
		// 中序遍历
		findKth(r.Left)
		k--
		if k == 0 {
			kv = r.Val
			return
		}
		findKth(r.Right)
	}
	findKth(root)
	return kv
}
*/
func kthSmallest(root *TreeNode, k int) int {
	var kv int
	var findKth func(r *TreeNode)
	findKth = func(r *TreeNode) {
		if r == nil || k == 0 {
			return
		}
		// 中序遍历
		findKth(r.Left)
		k--
		if k == 0 {
			kv = r.Val
			return
		}
		findKth(r.Right)
	}
	findKth(root)

	return kv
}