python二叉树非递归遍历

在Python中，二叉树的非递归遍历主要有三种方法：前序遍历、中序遍历和后序遍历。非递归遍历通常通过栈数据结构来实现，因为递归遍历会涉及到函数的调用堆栈，而栈恰好能模拟这个过程。

1. **前序遍历** (Preorder Traversal): 先访问根节点，然后递归地遍历左子树，最后遍历右子树。非递归版本通常是这样的：

   def preorder_traversal(root):
       if root is None:
           return []
       stack, output = [root], []
       while stack:
           node = stack.pop()
           output.append(node.val)
           if node.right:
               stack.append(node.right)
           if node.left:
               stack.append(node.left)
       return output

2. **中序遍历** (Inorder Traversal): 先递归地遍历左子树，然后访问根节点，最后遍历右子树。非递归版本可以这样实现：

   def inorder_traversal(root):
       stack, output = [], []
       while True:
           while root:
               stack.append(root)
               root = root.left
           if not stack:
               break
           node = stack.pop()
           output.append(node.val)
           root = node.right
       return output

3. **后序遍历** (Postorder Traversal): 先递归地遍历左右子树，最后访问根节点。非递归版本类似这样：

   def postorder_traversal(root):
       if root is None:
           return []
       stack1, stack2 = [root], []
       output = []
       while stack1:
           node = stack1.pop()
           stack2.append(node)
           if node.left:
               stack1.append(node.left)
           elif node.right:
               stack1.append(node.right)
       while stack2:
           output.append(stack2.pop().val)
       return output