先序遍历怎么写出完整代码
时间: 2023-07-03 17:32:18 浏览: 78
先序遍历(Preorder Traversal)是二叉树遍历的一种方式,其遍历顺序为根节点 -> 左子树 -> 右子树。下面是先序遍历的完整代码实现(假设二叉树的节点定义为一个包含左右子节点和值的结构体Node):
```python
class Node:
def __init__(self, val=None, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorderTraversal(root: Node) -> List[int]:
if not root:
return []
res = []
stack = [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
```
上述代码中,我们使用了一个栈来存储节点,首先将根节点入栈,之后每次弹出栈顶元素,并将其值加入结果列表中。如果该节点存在右子节点,则将右子节点入栈;如果该节点存在左子节点,则将左子节点入栈。重复上述步骤直到栈为空,最终返回结果列表即可。