用非递归算法写二叉树的先序遍历
时间: 2023-11-14 08:19:47 浏览: 39
非递归算法写二叉树的先序遍历需要借助栈来实现。具体步骤如下:
1. 建立一个栈,并将根节点压入栈中。
2. 当栈不为空时,执行以下操作:
- 弹出栈顶元素,将其值加入结果列表中。
- 如果该节点存在右子树,则将其右子节点压入栈中。
- 如果该节点存在左子树,则将其左子节点压入栈中。
3. 当所有节点都被遍历完后,返回结果列表。
下面是 Python 代码实现:
```python
def preorderTraversal(root):
if not root:
return []
stack, res = [root], []
while stack:
node = stack.pop()
res.append(node.val)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return res
```
其中,root 表示二叉树的根节点,val 表示该节点的值。
相关问题
一个非递归算法写出先序遍历最后一个数
先序遍历的顺序是:根节点 -> 左子树 -> 右子树。
非递归的先序遍历算法可以使用栈来实现。算法流程如下:
1. 将根节点入栈;
2. 当栈不为空时,执行以下步骤:
- 弹出栈顶元素,输出该元素的值;
- 如果该元素有右子树,将右子树入栈;
- 如果该元素有左子树,将左子树入栈;
3. 当栈为空时,遍历结束。
最后一个数即为最后弹出的数,也就是最后一个出栈的数。
下面是一个示例代码实现:
```python
def last_preorder(root):
stack = [root]
last = None
while stack:
node = stack.pop()
if node:
last = node.val
stack.append(node.right)
stack.append(node.left)
return last
```
其中,`root` 是二叉树的根节点,`val` 是二叉树节点的值。`last` 变量用于记录最后一个输出的节点的值。
完成二叉树先序遍历的非递归算法
好的,以下是二叉树先序遍历的非递归算法:
1. 新建一个栈,将根节点压入栈中。
2. 当栈不为空时,执行以下操作:
a. 弹出栈顶元素并输出该元素。
b. 如果该元素的右子树不为空,则将右子树压入栈中。
c. 如果该元素的左子树不为空,则将左子树压入栈中。
3. 重复步骤2,直到栈为空。
这个算法的思路是先访问根节点,然后将右子树压入栈中,再将左子树压入栈中,保证左子树先于右子树被访问。由于是非递归算法,需要用栈来模拟递归过程。