剑指 54. 二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第k大的节点。

//go 迭代；时空都是：平衡时：O(logN+K)； 不平衡时：O(N+K)
func kthLargest(root *TreeNode, k int) int {
    queue := []*TreeNode{}
    for root != nil || len(queue) > 0 {
        n := len(queue)
        if root != nil {
            queue = append(queue, root)
            root = root.Right
        } else {
            node := queue[n-1]
            queue = queue[:n-1]
            k--
            if k == 0 {
                return node.Val
            }
            root = node.Left
        }
    }
    return 0
}