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?
[qestion](https://leetcode.com/problems/kth-smallest-element-in-a-bst/#/description , question)
解法：
- 通過in-order排序將node變成一個array arr[k]就會是答案
while薇芝， 在follow up 里面焕阿，出現(xiàn)的問題在于如果頻繁的isnert和delete的話時間上就hold不住，每次insert or add之后都會出現(xiàn)需要重新in order的問題洁灵，假設我們insert n次，那么我們的時間總長就會變成n2,which is pretty bad
2.我使用的是這個解法掺出，只是個思路徽千，但是確實可行，需要改變binary tree的結構實現(xiàn)
class Solution(object):
def totalnode(self,root):
if not root.right and not root.left:
return 1
else:
l,r = 0, 0
if node.right:
r = self.totalnode(node.right)
if node.left:
l = self.totalnode(node.left)
return 1+l + r
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
if k == 0:
return root.val
l = 0
if root.left:
l = self.totalnode(l)
if k == l+1:
return root.val
if k > l+1:
return kthSmallest(self, root.right, k-l+1)
else:
return kthSmallest(self, root.right, k-1)
簡單來說用total-node function來計算某棵樹總共有多少node汤锨，
先計算左邊總共有多少node双抽，如果k > lefttotal,那么說明k在樹杈的右邊，反之就說明他在樹叉的左邊闲礼，但這樣的時間復雜度相當?shù)母咧笖?shù)性的牍汹，
但是，如果改變binary tree的結構的話柬泽，就能夠讓他的time complexity壓縮到n慎菲，
具體：
正常的tree
struct tree{
int val
tree left
tree right
}
但是可以加兩個屬性
struct tree{
int val
tree left
int lefttotal
tree right
int righttotal
}
通過兩個值來承載左邊的總數(shù)和右邊的總數(shù)，
具體操作是通過insert上每次insert進入更低層的時候锨并，根據(jù)她進入的方向露该，增加值，
這樣就不需要花時間來calculate total這兩個值第煮，但是使用的時候卻異常方便
leetcode沒把法改變固有結構有决，所以沒辦法實現(xiàn)，但是這種tree實現(xiàn)起來其實也很簡單空盼。
