实现二叉树的中序遍历和后序遍历的递归和非递归算法

在数据结构中，二叉树的中序遍历和后序遍历是非常基础的操作，以下是它们的递归和非递归实现：

### 递归实现：

#### 中序遍历 (左-根-右):

# 定义节点
class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal_recursive(node):
    if node is not None:
        inorder_traversal_recursive(node.left)
        print(node.val)  # 输出当前节点值
        inorder_traversal_recursive(node.right)

#### 后序遍历 (左-右-根):

def postorder_traversal_recursive(node):
    if node is not None:
        postorder_traversal_recursive(node.left)
        postorder_traversal_recursive(node.right)
        print(node.val)  # 输出当前节点值

非递归实现需要借助栈数据结构：

### 非递归实现 - 中序遍历:

def inorder_traversal_iterative(root):
    stack, output = [], []
    curr = root

    while True:
        while curr is not None:
            stack.append(curr)
            curr = curr.left

        if not stack:
            break

        curr = stack.pop()
        output.append(curr.val)

        curr = curr.right

    return output

### 非递归实现 - 后序遍历:

def postorder_traversal_iterative(root):
    if root is None:
        return []

    stack, output = [root], []
    while stack:
        node = stack.pop()

        if node.left is not None:
            stack.append(node.left)
        elif node.right is not None:
            stack.append(node.right)

        # 当前节点已无子节点，将其值加入结果
        else:
            output.append(node.val)

    return output[::-1]  # 因为后序遍历的结果通常是先右后左，所以反转一下