python之先序遍历

在Python中，先序遍历是一种用于树形数据结构（如二叉树）的方法，访问顺序是根节点 -> 左子节点 -> 右子节点。这是一种递归的方式，对于每个节点：

1. 首先访问当前节点（根节点）
2. 然后递归地遍历左子树（如果存在）
3. 最后递归地遍历右子树（如果存在）

下面是一个简单的例子，用递归函数实现二叉树的先序遍历：

def preorder_traversal(root):
    if root is not None:
        # 访问根节点
        print(root.val, end=" ")
        # 递归遍历左子树
        preorder_traversal(root.left)
        # 递归遍历右子树
        preorder_traversal(root.right)

# 使用示例
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 创建一个简单的二叉树
root = TreeNode(1, TreeNode(2), TreeNode(3))

当你运行上述代码，会得到类似这样的输出：1 2 3，表示按照先序遍历的顺序。

相关问题

python链表先序遍历二叉树

下面是用Python实现二叉树的先序遍历：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        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

首先定义一个`TreeNode`类表示二叉树中的每个节点，包含一个值`val`和左右子节点`left`和`right`。然后，在`Solution`类中，定义一个`preorderTraversal`方法，接收根节点`root`作为参数，返回先序遍历的结果。

首先判断根节点是否为空，如果为空，则直接返回空列表。然后创建一个栈，将根节点入栈。当栈不为空时，弹出栈顶节点，将其值`val`加入结果列表中。然后，将其右子节点（如果有）和左子节点（如果有）依次入栈。重复上述操作，直到栈为空，最后返回结果列表即可。

注意，这里用的是迭代法实现先序遍历，还有递归法实现先序遍历，两种方法都可以。

python先序遍历二叉树

以下是Python实现二叉树先序遍历的代码示例：

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 先序遍历二叉树
def preorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def preorder(root):
        if not root:
            return
        res.append(root.val)
        preorder(root.left)
        preorder(root.right)
    preorder(root)
    return res

以上代码中，我们首先定义了一个二叉树节点类`TreeNode`，包含节点值`val`、左子节点`left`和右子节点`right`。然后定义了一个`preorderTraversal`函数，用于实现先序遍历二叉树。在函数中，我们定义了一个辅助函数`preorder`，用于递归遍历二叉树。具体实现中，我们先将当前节点的值加入结果列表`res`中，然后递归遍历左子树和右子树。