二叉树前序遍历 非递归 python
二叉树的前序遍历是一种非常常见的树遍历方法，它遵循的顺序是根节点 -> 左子树 -> 右子树。在非递归实现中，我们通常会使用一个栈（Stack）来帮助我们完成这个操作。这是因为栈可以帮助我们记住需要处理的节点，这样我们就可以在遍历过程中返回到之前的节点，或者跳过一些不需要处理的节点。
以下是一个非递归的 Python 实现：
python
class TreeNode:
def __init__(self, x):
self.val = x二叉树中序遍历非递归算法
self.left = None
self.right = None
def preorderTraversal(root):
if root is None:
return []
stack, output = [root, ], []
while stack:
root = stack.pop()
if root is not None:
output.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)
return output
在这个代码中，我们首先检查根节点是否为空。如果为空，那么就返回一个空列表。然后，我们创建一个栈，并把根节点放入栈中。同时，我们创建一个空的输出列表。
然后，我们进入一个循环，这个循环会一直运行，直到栈变为空。在每次循环中，我们都会从栈中弹出一个节点。如果这个节点不是空，我们就把它加入到输出列表中。然后，我们会检查这个节点的右子节点和左子节点。如果右子节点存在，我们就把它加入到栈中。如果左子节点存在，我们也把它加入到栈中。需要注意的是，我们先加入右子节点，然后再加入左子节点。这是因为栈是后进先出（LIFO）的，所以左子节点会先被处理。
最后，当栈变为空时，我们就遍历了整个二叉树。返回的输出列表就是前序遍历的结果。
这种方法的时间复杂度是 O(n)，其中 n 是二叉树的节点数量。这是因为每个节点都会被访问一次，而且只会访问一次。空间复杂度也是 O(n)，因为我们需要一个栈来存储所有的节点。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。