LeetCode 230 Kth Smallest Element in a BST (中序遍历)

本文主要是介绍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 (中序遍历)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---