BST第K小元素

一句话说明

BST 的中序遍历天然有序，所以第 K 小就是中序走到第 K 个节点。

Go 代码

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
 
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return root.Val
        }
        root = root.Right
    }
    return -1
}

为什么能提前停

中序本来就是从小到大，数到第 k 个就可以直接返回。

相关主题

• 中序遍历
• BST查找
• 树算法

---

返回：树算法 | 算法学习导航