二叉树的前序遍历：递归与迭代方法

二叉树的前序遍历是一种常见的树遍历方法，其顺序为：根节点、左子树、右子树。在进行前序遍历时，我们需要访问每个节点，并按照特定的顺序进行操作。以下是两种实现前序遍历的方法：递归和迭代。
递归方法
递归是解决二叉树遍历问题的一种直观方法。在Python中，递归实现前序遍历的代码可能如下所示：

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def preorderTraversal(root):
if root is None:
return []
res = []
res.append(root.val)  # 访问根节点
res.extend(preorderTraversal(root.left))  # 递归遍历左子树
res.extend(preorderTraversal(root.right))  # 递归遍历右子树
return res

在这个代码中，我们首先检查根节点是否为空。如果为空，则返回空列表。否则，我们将根节点的值添加到结果列表中，然后递归地遍历左子树和右子树。最后返回结果列表。
迭代方法
除了递归之外，我们还可以使用迭代方法实现前序遍历。以下是使用Python实现的代码：

def preorderTraversal(root):
if root is None:
return []
res, stack = [], [root]
while stack:
node = stack.pop()  # 弹出栈顶元素，并访问该节点
if node:  # 如果节点不为空，则将其值添加到结果列表中
res.append(node.val)
if node.right:  # 将右子节点添加到栈中（如果存在）
stack.append(node.right)
if node.left:  # 将左子节点添加到栈中（如果存在）
stack.append(node.left)
return res

在这个代码中，我们首先检查根节点是否为空。如果为空，则返回空列表。否则，我们创建一个空的结果列表和一个包含根节点的栈。然后，在栈不为空的情况下，我们重复以下操作：弹出栈顶元素并访问该节点，如果节点不为空，则将其值添加到结果列表中。然后，我们将右子节点和左子节点（如果存在）依次添加到栈中。最后返回结果列表。需要注意的是，在将节点添加到栈中时，我们首先将右子节点添加到栈中（如果存在），然后再将左子节点添加到栈中（如果存在）。这是因为栈是后进先出的数据结构，先添加右子节点可以保证左子节点在右子节点之前被访问。