用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]:
    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

这个实现使用了一个栈来模拟递归过程，时间复杂度为 O(n)，其中 n 是二叉树的节点数。

相关问题

实现建立二叉树先序遍历中序遍历后序遍历用栈实现中序遍历输出叶子结点、个数输出结点、个数树深度退出的完整代码

在使用栈来实现二叉树的先序（Preorder）、中序（Inorder）、后序（Postorder）遍历以及特定需求如输出叶子节点、计算节点总数和树的深度时，首先我们需要创建一个二叉树节点结构，并设置相关的递归或迭代方法。这里是一个基本的Python示例：

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

# 先序遍历 (根-左-右)
def preorder_traversal(root):
    if root is not None:
        print(root.val, end=" ")  # 打印节点值
        preorder_traversal(root.left)  # 左子树
        preorder_traversal(root.right)  # 右子树

# 中序遍历 (左-根-右)
def inorder_traversal(root):
    stack = []
    current = root
    while True:
        while current is not None:
            stack.append(current)
            current = current.left
        if not stack:
            break
        node = stack.pop()
        print(node.val, end=" ")
        current = node.right

# 输出所有叶子节点 (辅助函数)
def get_leaf_nodes(root):
    leaves = []
    if root is not None and root.left is None and root.right is None:
        leaves.append(root.val)
    return leaves

# 计算节点总数
def count_nodes(root):
    if root is None:
        return 0
    else:
        return 1 + count_nodes(root.left) + count_nodes(root.right)

# 计算树的深度
def depth_of_tree(root):
    if root is None:
        return 0
    else:
        left_depth = depth_of_tree(root.left)
        right_depth = depth_of_tree(root.right)
        return max(left_depth, right_depth) + 1

# 示例用法
# 创建二叉树...
# ...
root = ...  # 初始化你的二叉树根节点

print("前序遍历: ", end="")
preorder_traversal(root)
print("\n中序遍历: ", end="")
inorder_traversal(root)

leaf_nodes = get_leaf_nodes(root)
print(f"叶节点: {leaf_nodes}")
print(f"叶节点数量: {len(leaf_nodes)}")

node_count = count_nodes(root)
print(f"节点总数: {node_count}")

tree_depth = depth_of_tree(root)
print(f"树的深度: {tree_depth}\n")

请注意，你需要根据实际需要调整这些函数，并提供二叉树的实例化代码。上述代码假设了二叉树的节点结构和一些基本操作已经定义好。如果你还没有定义这些，那么你需要首先定义`TreeNode`类。

二叉树先序遍历和中序遍历求后序遍历的代码

以下是二叉树先序遍历和中序遍历求后序遍历的代码：

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

def buildTree(preorder, inorder):
    if not preorder:
        return None
    
    root_val = preorder[0]
    root = TreeNode(root_val)
    
    i = inorder.index(root_val)
    
    root.left = buildTree(preorder[1:i+1], inorder[:i])
    root.right = buildTree(preorder[i+1:], inorder[i+1:])
    
    return root

def postorderTraversal(root):
    if not root:
        return []
    
    res = []
    stack = [(root, False)]
    
    while stack:
        node, visited = stack.pop()
        
        if not node:
            continue
        
        if visited:
            res.append(node.val)
        else:
            stack.append((node, True))
            stack.append((node.right, False))
            stack.append((node.left, False))
    
    return res

preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]

root = buildTree(preorder, inorder)
res = postorderTraversal(root)
print(res)

其中，`buildTree` 函数用于根据先序遍历和中序遍历构建二叉树，`postorderTraversal` 函数用于求二叉树的后序遍历。时间复杂度为 $O(n)$，空间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点个数。