题目描述
给定一个二叉树,请返回它的中序遍历。
请使用 非递归 方法。
样例
输入:[1,null,2,3]
1
\
2
/
3
输出:[1,3,2]
算法
(栈模拟递归) $O(n)$
如果用递归方法做,我们在处理每个节点时,要按照 左子树 => 根节点 => 右子树的顺序进行遍历,如下所示:
void dfs(TreeNode *u)
{
if (!u) return;
dfs(u->left);
cout << u->val << ' ';
dfs(u->right);
}
可以用栈来模拟这个过程。栈中每个元素存储两个值:TreeNode节点和一个整型的标记。
- 标记 = 0,表示还没遍历该节点的左子树;
- 标记 = 1,表示已经遍历完左子树,但还没遍历右子树;
- 标记 = 2,表示已经遍历完右子树;
然后我们可以根据标记的值,来分别处理各种情况:
- 标记 = 0,则将该节点的标记改成1,然后将其左儿子压入栈中;
- 标记 = 1,则说明左子树已经遍历完,将根节点的值插入答案序列中,然后将该节点的标记改成2,并将右儿子压入栈中;
- 标记 = 2,则说明以该节点为根的子树已经遍历完,直接从栈中弹出即可;
时间复杂度分析:树中每个节点仅会遍历一遍,且进栈出栈一次,所以时间复杂度是 $O(n)$。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<pair<TreeNode*, int>>sta;
sta.push(make_pair(root, 0));
while (!sta.empty())
{
if (sta.top().first == NULL)
{
sta.pop();
continue;
}
int t = sta.top().second;
if (t == 0)
{
sta.top().second = 1;
sta.push(make_pair(sta.top().first->left, 0));
}
else if (t == 1)
{
res.push_back(sta.top().first->val);
sta.top().second = 2;
sta.push(make_pair(sta.top().first->right, 0));
}
else sta.pop();
}
return res;
}
};
浙大数据结构对于非递归中序遍历是如此讲解的,学会了过来分享一下下~
棒!
可以直接将这个做法发到题解中,点“题解”——“LeetCode“,页面左上方有个按钮可以发题解~
发好了hhh
好棒!已赞
if (!s.empty())应该是不需要的吧,不可能为空
和大佬的类似,不过把标记作为NULL,感觉简单些。
It is a best solution found that very popular and helpful
https://www.youtube.com/watch?v=WHUMCUuktJk&ab_channel=EricProgramming
哈哈,突然发现自己的思路和大佬的一样,我也想标记一下用一个栈,但是觉得太复杂,就看着递归的写出了楼上的算法,不过标记法应该是要比递归模拟要好一些,毕竟递归模拟那种方法其实两次while有重复访问节点的情况,在leetcode测试的时候还没有递归的速度快
这道题目用标记法会好一些,代码简单一些,效率也会高一些hh
上面题解里是用一套机械的方式直接将递归改成非递归,效率会低一些,不过通用性比较强。