230._kth_smallest_element_in_a_bst.md

### 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位


```python
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