用非递归算法遍历二叉树的叶子结点
时间: 2023-05-26 18:03:49 浏览: 129
非递归算法遍历二叉树的叶子节点,可以使用栈或队列来实现。
1. 使用栈
先将根节点入栈,然后循环执行以下操作:
- 弹出栈顶的节点,如果该节点有左子节点,则将左子节点入栈;
- 如果该节点有右子节点,则将右子节点入栈;
- 如果该节点是叶子节点,则输出该节点的值。
代码实现如下:
```
void traversalLeaves(Node* root) {
if (root == nullptr) {
return;
}
stack<Node*> st;
st.push(root);
while (!st.empty()) {
Node* cur = st.top();
st.pop();
if (cur->left != nullptr) {
st.push(cur->left);
}
if (cur->right != nullptr) {
st.push(cur->right);
}
if (cur->left == nullptr && cur->right == nullptr) {
cout << cur->val << " ";
}
}
}
```
2. 使用队列
先将根节点入队列,然后循环执行以下操作:
- 弹出队首的节点,如果该节点有左子节点,则将左子节点入队列;
- 如果该节点有右子节点,则将右子节点入队列;
- 如果该节点是叶子节点,则输出该节点的值。
代码实现如下:
```
void traversalLeaves(Node* root) {
if (root == nullptr) {
return;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
if (cur->left != nullptr) {
q.push(cur->left);
}
if (cur->right != nullptr) {
q.push(cur->right);
}
if (cur->left == nullptr && cur->right == nullptr) {
cout << cur->val << " ";
}
}
}
```