Kth Smallest Element in a BST

这个题不管怎么变算法，都是做不到O(h)的，因为题目中并没有明确表明BST的结构是否完整，如果就是一颗普通的BST，我们最终也只能通过中序遍历找到这个点，所谓的二分法其实还是一个个统计了结点的，没有太多意义，但是如果能改变BST的结构，我们可以通过将结点中设置一个count属性来统计当前节点是BST的第几个结点，这样以后再query时我们就可以利用这个节省时间了

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        count = 0
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                count += 1
                if count == k:
                    return root.val
                root = root.right

        return -1

这里有一种一般情况下是O(lgn)的解法，其思想和kth largest number in array差不多，统计半边元素的数量，然后逐步将问题规模缩小

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        count = self.countNode(root.left)
        if k <= count:
            return self.kthSmallest(root.left, k)
        elif k > count + 1:
            return self.kthSmallest(root.right, k - count - 1)
        return root.val

    def countNode(self, root):
        if not root:
            return 0
        return self.countNode(root.left) + 1 + self.countNode(root.right)