能否用Python实现单栈非递归的二叉树前序、中序、后序统一遍历（时间复杂度O(N)、空间复杂度O(N)）？

Absolutely! I've got you covered. Implementing all three binary tree traversals using a single stack (no recursion) while maintaining O(N) time and space complexity is totally feasible. Let's walk through each traversal with clear code and explanations.

First, let's define our basic TreeNode class to represent the binary tree nodes:

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

Preorder Traversal (Root → Left → Right) #

The preorder approach is straightforward: we start with the root node, visit it first, then push its right child to the stack (since stacks are LIFO, we push right first so left gets processed next), followed by the left child. We repeat this until the stack is empty.

def preorder_traversal(root):
    if not root:
        return []
    
    stack = [root]
    result = []
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        # Push right first so left is processed next
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    return result

Explanation: Each node is pushed and popped exactly once, so time complexity is O(N). The stack can hold up to O(N) nodes in the worst case (e.g., a skewed tree), so space complexity is O(N).

Inorder Traversal (Left → Root → Right) #

For inorder, we need to traverse all left children first before visiting the root, then process the right subtree. We'll use a pointer to track the current node, pushing all left descendants to the stack until we hit a null, then pop and visit the node, then move to its right child.

def inorder_traversal(root):
    if not root:
        return []
    
    stack = []
    result = []
    current = root
    
    while current or stack:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        current = stack.pop()
        result.append(current.val)
        # Move to the right subtree
        current = current.right
    
    return result

Explanation: Again, each node is pushed and popped once, so time is O(N). The stack size peaks at O(N) for skewed trees, so space is O(N).

Postorder Traversal (Left → Right → Root) #

Postorder is trickier because we need to visit both children before the root. A common approach is to use a flag to track whether a node's children have been processed. We'll push tuples of (node, visited) onto the stack:

• When we first push a node, visited is False
• When we pop a node with visited=False, we push it back with visited=True, then push its right child (unvisited), then left child (unvisited)
• When we pop a node with visited=True, we can safely add its value to the result

def postorder_traversal(root):
    if not root:
        return []
    
    stack = [(root, False)]
    result = []
    
    while stack:
        node, visited = stack.pop()
        if visited:
            result.append(node.val)
        else:
            # Push node back as visited, then right, then left
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
    
    return result

Explanation: Each node is pushed and popped twice (once unvisited, once visited), but that still totals O(N) operations. The stack holds at most O(N) nodes, so space remains O(N).

Test It Out! #

Let's put it all together with a sample binary tree to verify:

# Build a sample tree:
#       1
#        \
#         2
#        /
#       3
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

print("Preorder:", preorder_traversal(root))   # Output: [1, 2, 3]
print("Inorder:", inorder_traversal(root))    # Output: [1, 3, 2]
print("Postorder:", postorder_traversal(root))# Output: [3, 2, 1]

All three traversals work as expected, with the required time and space complexity.

内容的提问来源于stack exchange，提问作者Rahul Jangir