54.md

二叉搜索树的第k个结点

题目

给定一棵结点数为 n 二叉搜索树，请找出其中的第 k 小的TreeNode结点。

要求：空间复杂度 O(1)，时间复杂度 O(n)

注意：不是返回结点的值

示例

输入：{5,3,7,2,4,6,8},3

返回值：4

说明：按结点数值升序顺序可知第三小结点的值为4 ，故返回对应结点值为4的结点即可

思路

• 遍历树，所有节点放在数组里，排序取值
• 中序遍历顺序即为从小到大的访问顺序

为什么？

• 因为二叉搜索树的特点就是： 左节点 > 根节点 > 右节点
• 中序遍历又是先打印它的左子树，然后再打印它本身，最后打印它的右子树

实现

var res *TreeNode

func KthNode(pRoot *TreeNode, k int) *TreeNode {
	inOrder(pRoot, &k)
    if res != nil {
        res.Left = nil
        res.Right = nil
    }
	return res
}

func inOrder(root *TreeNode, k *int) {
	if root == nil {
		return
	}
	inOrder(root.Left, k)
	*k -= 1
	if *k == 0 {
		res = root
		return
	}
	inOrder(root.Right, k)
}