C++编写先序遍历的非递归算法
时间: 2023-12-03 08:03:44 浏览: 26
下面是C++编写的先序遍历非递归算法:
```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> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> s;
if (root != nullptr) {
s.push(root); // 将根节点入栈
}
while (!s.empty()) {
TreeNode* node = s.top();
s.pop(); // 弹出栈顶节点
res.push_back(node->val); // 将节点值加入到结果中
if (node->right != nullptr) {
s.push(node->right); // 右子树入栈
}
if (node->left != nullptr) {
s.push(node->left); // 左子树入栈
}
}
return res;
}
};
```
该算法利用了栈来模拟递归过程,先将根节点入栈,然后每次弹出栈顶节点,并将其值加入到结果中,接着将右子树和左子树依次入栈。