題目

給定一個(gè)二叉搜索樹的根節(jié)點(diǎn) root ，和一個(gè)整數(shù) k ，請(qǐng)你設(shè)計(jì)一個(gè)算法查找其中第 k 個(gè)最小元素（從 1 開始計(jì)數(shù)）。

示例

輸入：root = [5,3,6,2,4,null,null,1], k = 3
輸出：3

解析

這道題應(yīng)該是能做出來的，首先二叉搜索樹的中序遍歷是遞增的，那就在此基礎(chǔ)上直接數(shù)K個(gè)樹就好了

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func kthSmallest(root *TreeNode, k int) int {ans := 0if root == nil || k <= 0 {return ans}cur := rootstack := 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 // 大意了，這一行記錯(cuò)了，記成pushback了}}return ans
}