用先序非递归方法遍历二叉树。
时间: 2024-05-11 20:14:17 浏览: 54
使用栈来模拟先序遍历的过程:
1.将根节点压入栈中;
2.循环执行以下操作,直到栈为空:
(1)弹出栈顶元素,输出该元素的值;
(2)如果该元素的右子节点不为空,将其右子节点压入栈中;
(3)如果该元素的左子节点不为空,将其左子节点压入栈中。
例如,对于以下二叉树:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
其先序遍历结果为:1 2 4 5 3 6 7。
使用非递归方法实现代码如下:
```python
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def preorderTraversal(root: TreeNode):
if not root:
return []
stack = [root]
res = []
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
```
在代码中,首先判断根节点是否为空,如果为空则直接返回空列表。然后创建一个栈,将根节点压入栈中,并创建一个结果列表用于存储遍历结果。
循环执行弹出栈顶元素、输出该元素值、将右子节点和左子节点压入栈中的操作,直到栈为空。最终返回遍历结果列表。
阅读全文