230. 二叉搜索树中第K小的元素
描述
- 给定一个二叉搜索树，编写一个函数kthSmallest来查找其中第 k 个最小的元素。
说明
- 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例
示例 1:
输入: root = [3,1,4,null,2], k = 1
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
输出: 3
进阶
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k
小的值，你将如何优化kthSmallest函数？(参考)
思路
- 二叉搜索树的中序遍历是个有序数列，所以求第 k 小的元素就是求中序遍历中第 k 个元素。
- 两种实现方法，一种利用栈来实现的非递归算法，一种是递归算法。
- 非递归解法，利用栈，让代码跟着思路走
1）找到左子树最下边的节点，沿途的节点保存到栈中
2）访问这个节点
3）访问这个节点的右子树(对于程序而且，这是一棵新的树)，继续前面1 ~ 2的过程
4）从栈中取出一个节点访问(此时左子树肯定已将都访问完毕了)，访问其右子树。
class Solution_230_01 {
public:
int kthSmallest(TreeNode* root, int k) {
if (!root) return -1;
stack<TreeNode*> mStack;
TreeNode* node = root;
vector<int> ret;
while (node || !mStack.empty()) {
while (node) {
mStack.push(node);
node = node->left;
}
node = mStack.top();
mStack.pop();
if (--k == 0) return node->val;
node = node->right;
}
return -1;
}
};
class Solution_230_01 {
public:
int kthSmallest(TreeNode* root, int k) {
if(!root) return -1;
return inorderTraversal(root, k);
}
int inorderTraversal(TreeNode* node, int& k){
int ret = -1;
if(--k == 0) ret = node->val;
if(ret == -1 && node->left) ret = inorderTraversal(node->left, k);
if(ret == -1 && node->rihgt) ret = inorderTraversal(node->right, k);
return ret;
}
};
