题目描述
给定一个二叉树，返回它的中序 遍历。
题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> res2;
void mid_travel(TreeNode* root)
{
if (root)
{
mid_travel(root->left);
res2.push_back(root->val);
mid_travel(root->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
mid_travel(root);
return res2;
}
|
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
你是想说莫里斯遍历？巧了，我不会。写个基于栈的循环吧：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| vector<int> inorderTraversal2(TreeNode* root) {
if (!root)return{};
stack<TreeNode*> s;
vector<int> ret;
s.push(root);
TreeNode* tmp = root->left;
while (tmp)
{
s.push(tmp);
tmp = tmp->left;
}
while (!s.empty())
{
ret.push_back(s.top()->val);
tmp = s.top()->right;
s.pop();
while (tmp)
{
s.push(tmp);
tmp = tmp->left;
}
}
return ret;
}
|
两个时空比居然没太大差别？
多亏了官方题解的动图，才能这么快地一遍过。