230.Kth Smallest Element in a BST

本文主要是介绍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?

中序遍历BST

BST具有如下性质：

左子树中所有元素的值均小于根节点的值

右子树中所有元素的值均大于根节点的值

因此采用中序遍历（左 -> 根 -> 右）即可以递增顺序访问BST中的节点，从而得到第k小的元素，时间复杂度O(k)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:int kthSmallest(TreeNode* root, int k) {stack<TreeNode *> myStack;int count = 1;while(root || !myStack.empty()){while(root){myStack.push(root);root = root->left;}if(!myStack.empty()){TreeNode *tmp = myStack.top();myStack.pop();if(count == k){return tmp->val;}root = tmp->right;++count;}}return INT_MAX;}
};

进一步思考：

如果BST节点TreeNode的属性可以扩展，则再添加一个属性leftCnt，记录左子树的节点个数

记当前节点为node当node不为空时循环：若k == node.leftCnt + 1：则返回node否则，若k > node.leftCnt：则令k -= node.leftCnt + 1，令node = node.right否则，node = node.left

上述算法时间复杂度为O(BST的高度)

这篇关于230.Kth Smallest Element in a BST的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---