230. Kth Smallest Element in a BST

題目：

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. 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).

鏈接： ?http://leetcode.com/problems/kth-smallest-element-in-a-bst/

7/25/2017

2ms, 20%

好幾天終于有道自己做的題了。。。iterative inorder traversal

 1 public class Solution {
 2     public int kthSmallest(TreeNode root, int k) {
 3         Stack<TreeNode> 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，然后再從左右兩邊找

https://discuss.leetcode.com/topic/17810/3-ways-implemented-in-java-python-binary-search-in-order-iterative-recursive

python generator

https://discuss.leetcode.com/topic/18279/pythonic-approach-with-generator

更多討論

https://discuss.leetcode.com/category/238/kth-smallest-element-in-a-bst

轉載于:https://www.cnblogs.com/panini/p/7236107.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/455062.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/455062.shtml
英文地址，請注明出處：http://en.pswp.cn/news/455062.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！