二叉树的中序遍历(三种方法)
题目:
原题链接
简述题目就是:给你一颗二叉树的根结点root
返回它的中序遍历
方法一(递归):
中序遍历: 简单来说就是按照访问左子树——根节点——右子树的方式遍历这棵树,而在访问左子树或者右子树的时候我们按照同样的方式遍历,直到遍历完整棵树。口诀就是先左,再根,后右(看到这还是不明白的,可以自己查一下)
具体思路:
我们先定义root
表示当前访问的结点,如果该结点为空则直接返回。如果不为空,则递归访问这个结点的左子树,然后把当前结点的值加入答案res
中,然后递归访问该结点的右子树。
代码
class Solution {
public:
void inorder(TreeNode* root, vector<int>& res) {
if (!root)
return;
inorder(root->left, res);
res.push_back(root->val);
inorder(root->right, res);
}
vector<int> inorderTraversal(TreeNode* root)
{
vector<int> res;
inorder(root, res);
return res;
}
};
方法二(迭代)
具体思路:
按照上面递归是思路,我们只需要模拟出一个栈stk
即可。我们还是用root
来表示当前访问的结点,只要root
不为空或者栈stk
不为空我们就一直循环。先访问root
的左孩子,只要左孩子不为空,我们就把root
压入栈,并且把root=root->left
,一直循环直至左孩子为空。我们再把栈顶取出并把它加入到答案中,并让root=root->right
。
代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root != nullptr || !stk.empty()) {
while (root != nullptr) {
stk.push(root);
root = root->left;
}
root = stk.top();
stk.pop();
res.push_back(root->val);
root = root->right;
}
return res;
}
};
方法三(Morris遍历)
思路:
重要变量说明
root
:表示当前访问的结点
pre
:表示root
的左子树上最右的结点(即左子树中序遍历的最后一个结点,也可以称之为root
中序遍历的前驱结点)
- 如果
root
无左孩子,那就把root
加入答案数组,再令root=root->right
- 如果
root
有左孩子,那我们先找到pre
,- 如果
pre
为空,那我们就将pre->right=root
,再令root=root->left
。 - 如果
pre
不为空,那就说明root
的左子树已经访问完了,我们把root
加入答案,同时剪断链接pre->right=nullptr
(因为root
的左子树中最右的结点pre
本来没有右孩子,我们之前临时使pre
的右孩子为root
,这会打乱二叉树的结构,所以我们要还原),再令root=root->right
。
- 如果
- 一直循环直至遍历完整棵树。
代码
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
TreeNode *predecessor = nullptr;
while (root != nullptr) {
if (root->left != nullptr) {
// predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
predecessor = root->left;
while (predecessor->right != nullptr && predecessor->right != root) {
predecessor = predecessor->right;
}
// 让 predecessor 的右指针指向 root,继续遍历左子树
if (predecessor->right == nullptr) {
predecessor->right = root;
root = root->left;
}
// 说明左子树已经访问完了,我们需要断开链接
else {
res.push_back(root->val);
predecessor->right = nullptr;
root = root->right;
}
}
// 如果没有左孩子,则直接访问右孩子
else {
res.push_back(root->val);
root = root->right;
}
}
return res;
}
};
个人总结:
三种方法中第一中递归最好想也最好写,没什么思维难度,但是递归不安全,对于严重线性化的二叉树有可能栈溢出。第二种迭代的方法难度也不大,就是需要我们把递归中隐形的栈给手动模拟出来。难度最大的是第三种Morris方法遍历,这一部分涉及到线索化二叉树,一般学校中数据结构与算法分析这门课会将的(反正博主上这门课的时候老师讲了),了解了线索化二叉树之后再看Morris遍历方法会简单很多。
plus:
这里我只写了中序遍历的三种方法,前序遍历和后序遍历思路和这差不多,如果后面我有时间,我会把前序遍历和后序遍历的三种方法代码补上 (估计多半是没时间了)
写在最后
如果你觉得我写题解还不错的,请各位王子公主移步到我的其他题解看看
- 数据结构与算法部分(还在更新中):
- C++ STL总结 - 基于算法竞赛(强力推荐)
- 动态规划——01背包问题
- 动态规划——完全背包问题
- 动态规划——多重背包问题
- 动态规划——分组背包问题
- 最短路算法——Dijkstra(C++实现)
- 最短路算法———Bellman_Ford算法(C++实现)
- 最短路算法———SPFA算法(C++实现)
- 最小生成树算法———prim算法(C++实现)
- 最小生成树算法———Kruskal算法(C++实现)
- 染色法判断二分图(C++实现)
- Linux部分(还在更新中):
?🎉总结
“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”
如果有错误?,欢迎指正哟😋
🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!