### Python非递归算法构建二叉树并进行前序遍历的实现 在Python中，可以通过使用栈来实现二叉树的非递归前序遍历。以下是一个完整的代码示例，展示如何构建一个二叉树，并通过非递归方法对其进行前序遍历。 #### 构建二叉树节点类 首先定义一个二叉树节点类 `TreeNode`，用于存储节点值以及左右子节点的引用。 ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right ``` #### 非递归前序遍历实现 以下是基于栈的非递归前序遍历实现： ```python def preorderTraversal(root): if root is None: return [] stack, result = [root], [] # 初始化栈和结果列表 while stack: node = stack.pop() # 弹出栈顶元素 result.append(node.val) # 访问当前节点 # 先将右子节点压入栈（如果存在），再将左子节点压入栈（如果存在） # 这样可以确保左子节点先被访问 if node.right: stack.append(node.right) if node.left: stack.append(node.left) return result ``` #### 测试代码 以下是一个测试用例，展示如何构建二叉树并进行前序遍历。 ```python # 构建二叉树 # 1 # / \ # 2 3 # / \ # 4 5 root = TreeNode(1) root.left = TreeNode(2) root.right = TreeNode(3) root.left.left = TreeNode(4) root.left.right = TreeNode(5) # 调用前序遍历函数 output = preorderTraversal(root) print("前序遍历结果:", output) # 输出应为 [1, 2, 4, 5, 3] ``` 上述代码实现了非递归的前序遍历[^2]，通过栈来模拟递归调用的过程。每次从栈中弹出一个节点时，将其值添加到结果列表中，然后按照“右子节点先入栈，左子节点后入栈”的顺序压入栈中，以确保左子节点优先被访问。 ### 注意事项 - 在非递归前序遍历中，栈的作用是保存尚未处理的节点。 - 该方法的时间复杂度为 O(n)，其中 n 是二叉树中的节点数，因为每个节点仅被访问一次。 - 空间复杂度为 O(h)，其中 h 是二叉树的高度，最坏情况下栈的空间需求与树的高度成正比。