题目：

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?

Hint:

1. 1. Try to utilize the property of a BST.
   2. What if you could modify the BST node's structure?
   3. The optimal runtime complexity is O(height of BST).

链接：  

7/25/2017

2ms, 20%

好几天终于有道自己做的题了。。。iterative inorder traversal

1 public class Solution { 2     public int kthSmallest(TreeNode root, int k) { 3         Stack
     
       stack = new Stack<>(); 4         TreeNode node = root; 5         int kthSml = 0; 6          7         while((node != null || !stack.isEmpty()) && k > 0) { 8             while (node != null) { 9                 stack.push(node);10                 node = node.left;11             }12             node = stack.pop();13             kthSml = node.val;14             k--;15             node = node.right;16         }17         return kthSml;18     }19 }
     

别人的答案

可以利用DFS求root的count，然后再从左右两边找

python generator

r

更多讨论