题目描述
给定一个二叉树，返回它的 前序 遍历。进阶: 递归算法很简单，你可以通过迭代算法完成吗？
题解
1
2
3
4
5
6
7
8
9
10
11
12
| void preorder(TreeNode* root, vector<int>& vec)
{
if (!root)return;
vec.push_back(root->val);
preorder(root->left,vec);
preorder(root->right,vec);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res = {};
preorder(root, res);
return res;
}
|
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.3 MB, 在所有 C++ 提交中击败了100.00%的用户
既如此，何必用迭代？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<int> preorderTraversal2(TreeNode* root) {
vector<int> res = {};
stack<TreeNode*> st;
if (!root)return{};
st.push(root);
TreeNode* tmp;
while (!st.empty())
{
tmp = st.top();
st.pop();
res.push_back(tmp->val);
if (tmp->right)
st.push(tmp->right);
if (tmp->left)
st.push(tmp->left);
}
return res;
}
|
执行用时 :4 ms, 在所有 C++ 提交中击败了58.29%的用户
内存消耗 :8.7 MB, 在所有 C++ 提交中击败了100.00%的用户