遍历二叉树，如何避免代码重复

遍历二叉树是计算机科学中的一个基本问题，通常有三种主要的遍历方式：前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）和后序遍历（Post-order Traversal）。为了避免代码重复，可以使用递归或迭代的方法来实现这些遍历算法。

基础概念

前序遍历：根节点 -> 左子树 -> 右子树
中序遍历：左子树 -> 根节点 -> 右子树
后序遍历：左子树 -> 右子树 -> 根节点

递归方法

递归是最直观的实现方式，但可能会导致代码重复。以下是使用递归实现三种遍历方式的示例代码：

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

def pre_order_traversal(root):
    if root:
        print(root.value)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

def in_order_traversal(root):
    if root:
        in_order_traversal(root.left)
        print(root.value)
        in_order_traversal(root.right)

def post_order_traversal(root):
    if root:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.value)

迭代方法

为了避免递归带来的栈溢出风险和代码重复，可以使用迭代方法。迭代方法通常使用栈来模拟递归过程。以下是使用迭代实现三种遍历方式的示例代码：

def pre_order_traversal_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

def in_order_traversal_iterative(root):
    stack, result = [], []
    current = root
    while True:
        if current:
            stack.append(current)
            current = current.left
        elif stack:
            current = stack.pop()
            result.append(current.value)
            current = current.right
        else:
            break
    return result

def post_order_traversal_iterative(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.value)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]