230 kth smallest element in a bst
230. Kth Smallest Element in a BST
题目: https://leetcode.com/problems/kth-smallest-element-in-a-bst/
难度: Medium
跟昨天做的一道题类似，一上来就走取巧之路。
InOrder排序，输出，当然也完全可以用昨天的binary tree iterator,入stack,出stack,直到输出第k位
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.root = root
self.lst = []
self.inOrder(root)
return self.lst[k-1]
def inOrder(self, root):
if root == None:
return
self.inOrder(root.left)
self.lst.append(root.val)
self.inOrder(root.right)
现在看到kth 就条件反射的想用divide & conquer, 扫root的左子树看nodes量，如果nodes数量是k-1，那么node就刚好是第k个，如果大于k > 左子树数量，扫右子树，同时更新root为root.right。
看到的言论：
If we can change the BST node structure, We can add a new Integer to mark the number of element in the left sub-tree.
when the node is not null.
- if k == node.leftNum + 1, return node
- if k > node.leftNum + 1, make k -= node.leftNum + 1, and then node = node.right
- otherwise, node = node.left
