## 题目描述：

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.

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?

Hint:

Try to utilize the property of a BST.

What if you could modify the BST node's structure?

The optimal runtime complexity is O(height of BST).

BST具有如下性质：

## Python代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
# @param {TreeNode} root
# @param {integer} k
# @return {integer}
def kthSmallest(self, root, k):
stack = []
node = root
while node:
stack.append(node)
node = node.left
x = 1
while stack and x <= k:
node = stack.pop()
x += 1
right = node.right
while right:
stack.append(right)
right = right.left
return node.val

Pingbacks已关闭。