本文主要是介绍LeetCode 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.
Example 1:
Input: root = [3,1,4,null,2], k = 13/ \1 4\2 Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 35/ \3 6/ \2 4/1 Output: 3
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?
题目链接：https://leetcode.com/problems/kth-smallest-element-in-a-bst/
题目分析：中序遍历即可，至于follow up，对每个点记录其子树的size即可，插入删除操作只需修改到根路径上点的size即可
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public int kthSmallest(TreeNode root, int k) {int cnt = 0, ans = 0;Stack<TreeNode> stk = new Stack<>();while (root != null || !stk.empty()) {while (root != null) {stk.add(root);root = root.left;}if (!stk.empty()) {root = stk.pop();cnt++;if (cnt == k) {ans = root.val;break;}root = root.right;}}return ans;}
}
这篇关于LeetCode 230 Kth Smallest Element in a BST (中序遍历)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
