对于二叉树来说,中序遍历的顺序是: 左子树->根节点->右子树。中序是相对于根节点来说的。在实际操作中如果进行中序遍历呢,现在使用一道力扣的题来演示一下
230. 二叉搜索树中第K小的元素
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3
进阶:
如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
方法一: 递归
class Solution {
public:
stack<int>small;
void midorder(TreeNode* root, int k)
{
if(small.size() >= k)
return;
if(root == NULL)
return;
midorder(root->left, k);
if(small.size() >= k)
return;
small.push(root->val);
if(small.size() >= k)
return;
midorder(root->right, k);
}
int kthSmallest(TreeNode* root, int k) {
midorder(root, k);
return small.top();
}
};
方法二:迭代
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode*>small;
small.push(root);
while(!small.empty())
{
TreeNode* tmp = small.top();
if(tmp->left != NULL)
{
small.push(tmp->left);
tmp->left = NULL;
}
else
{
small.pop();
if(tmp->right != NULL)
small.push(tmp->right);
k--;
if(k <= 0)
return tmp->val;
}
}
return 0;
}
};
下图中第一行是采用的方法二,第二行采用的是方法一,也就是说虽然理论上,递归会比迭代更耗时,但实际由于所采用的数据结构的具体实现和编译器的代码优化,递归不见得比迭代要耗时,下图就是很好的一个佐证,但从上面的代码可以看出,在代码的理解层面,递归更简单易懂,易于代码的维护。