每日一练：二叉树的中序遍历
一、题目要求
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
二、解法1-递归 O(N)
中序遍历的次序是 左-根-右，使用递归很简单就能写出来
class Solution {
void _inorderTravinersal(TreeNode* root) {
if (root == nullptr)
return;
_inorderTravinersal(root->left); // 左
_v.push_back(root->val); // 根
_inorderTravinersal(root->right);// 右
}
public:
vector<int> inorderTraversal(TreeNode* root) {
_inorderTravinersal(root);
return _v;
}
private:
vector<int> _v;
};三、解法2-迭代 进阶
使用栈来模拟递归。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
stack<TreeNode*> s;
while (root != nullptr || s.empty() == false) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
v.push_back(root->val);
root = root->right; // 下一次循环检查是否有右
}
return v;
}
};原文地址：https://blog.csdn.net/2303_78095330/article/details/142465485
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！