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`中，然后递归遍历左子树和右子树。

相关问题

python先序遍历二叉树的非递归算法

以下是 Python 实现的二叉树先序遍历的非递归算法：

class TreeNode:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
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

该算法利用栈来实现非递归遍历二叉树，先将根节点入栈，然后依次弹出栈顶元素，将其值添加到结果列表中，并将其右子节点和左子节点入栈。由于栈的后进先出特性，先把右子节点入栈，再把左子节点入栈，保证了先遍历左子树。

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`加入结果列表中。然后，将其右子节点（如果有）和左子节点（如果有）依次入栈。重复上述操作，直到栈为空，最后返回结果列表即可。

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