二叉搜索树中第k小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

直接中序遍历

func kthSmallest(root *TreeNode, k int) int {
    rank := 0
    var res int
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        rank += 1
        if rank == k {
            res = root.Val
        }
        dfs(root.Right)
    }
    dfs(root)
    return res
}

存到hash表中

// 一次遍历多次查找
func kthSmallest(root *TreeNode, k int) int {
    var rankMap map[int]int
    rank := 0
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode) {
        if root == nil {
            return
        }
        dfs(root.Left)
        rank += 1
        rankMap[rank] = root.Val.(int)
        dfs(root.Right)
    }
    dfs(root)
    return rankMap[k]
}

用二叉平衡树

// 适用于经常要插入删除二叉树d