230. Kth Smallest Element in a BST ——迭代本质：a=xx1 while some_condition: a=xx2
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you
need to find the kth smallest frequently? How would you optimize the
kthSmallest routine?
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ # left first node = root nodes = [] n = 0 while node: nodes.append(node) node = node.left while nodes: node = nodes.pop() # min val n += 1 if n == k: return node.val node = node.right while node: nodes.append(node) node = node.left return None