题目
给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。
示例
输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3
解析
这道题应该是能做出来的,首先二叉搜索树的中序遍历是递增的,那就在此基础上直接数K个树就好了
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func kthSmallest(root *TreeNode, k int) int {
ans := 0
if root == nil || k <= 0 {
return ans
}
cur := root
stack := list.New()
for cur != nil || stack.Len() > 0 {
if cur != nil {
stack.PushBack(cur)
cur = cur.Left
} else {
cur = stack.Remove(stack.Back()).(*TreeNode)
k--
if k == 0 {
return cur.Val
}
cur = cur.Right // 大意了,这一行记错了,记成pushback了
}
}
return ans
}