对于二叉树来说,中序遍历的顺序是: 左子树->根节点->右子树。中序是相对于根节点来说的。在实际操作中如果进行中序遍历呢,现在使用一道力扣的题来演示一下
230 二叉搜索树中第K小的元素
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;
}
};
下图中第一行是采用的方法二,第二行采用的是方法一,也就是说虽然理论上,递归会比迭代更耗时,但实际由于所采用的数据结构的具体实现和编译器的代码优化,递归不见得比迭代要耗时,下图就是很好的一个佐证,但从上面的代码可以看出,在代码的理解层面,递归更简单易懂,易于代码的维护。
94 二叉树的中序遍历
94. 二叉树的中序遍历
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[2,1]
示例 5:
输入:root = [1,null,2]
输出:[1,2]
提示:
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-tree-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
递归算法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> store;
void inorder(TreeNode *root)
{
if(root == NULL)
return;
inorder(root->left);
store.push_back(root->val);
inorder(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
if(!store.empty())
store.clear();
inorder(root);
return store;
}
};
迭代算法
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ret;
if(root == nullptr)
return ret;
stack<TreeNode*>inorder;
inorder.push(root);
while(!inorder.empty())
{
TreeNode* tmp = inorder.top();
if(tmp->left != nullptr)
{
inorder.push(tmp->left);
tmp->left = nullptr;
}
else if(tmp->right != nullptr)
{
ret.push_back(tmp->val);
inorder.pop();
inorder.push(tmp->right);
}
else
{
ret.push_back(tmp->val);
inorder.pop();
}
}
return ret;
}
};