🥧递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
dfs(v, root);
return v;
}
void dfs(vector<int> &v, TreeNode* n)
{
if(!n)
return ;
if(n->left)
dfs(v, n->left);
v.push_back(n->val);
if(n->right)
dfs(v, n->right);
}
};
|
Accepted
68/68 cases passed (8 ms)
Your runtime beats 15.97 % of cpp submissions
Your memory usage beats 13.03 % of cpp submissions (9.9 MB)
🥧非递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> v;
if(!root)
return v;
stack<TreeNode* > stk;
stk.push(root);
while(stk.size())
{
auto nd = stk.top();
stk.pop();
if(nd->right)
stk.push(nd->right);
if(!nd->left && !nd->right)
v.push_back(nd->val);
else {
stk.push(nd);
}
if(nd->left)
stk.push(nd->left);
nd->left = nullptr;
nd->right = nullptr;
}
return v;
}
};
|
Accepted
68/68 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 65.81 % of cpp submissions (9.1 MB)
