实现一个二叉树的中序遍历，要求分别使用递归和迭代两种方法。

Question

Accepted Answer

中序遍历是二叉树遍历的一种方式，其顺序是先遍历左子树，然后访问根节点，最后遍历右子树。以下是递归和迭代两种方法的实现：
递归方法：递归方法比较简单，只需要按照中序遍历的顺序递归调用即可。以下是 Python 代码：
python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorder_traversal_recursive(root):
    result = []
    def helper(node):
        if node:
            helper(node.left)
            result.append(node.val)
            helper(node.right)
    helper(root)
    return result
迭代方法：迭代方法需要使用栈来模拟递归调用的过程。首先将根节点及其所有左子节点压入栈中，然后依次弹出栈顶元素，访问该元素，并将其右子节点及其所有左子节点压入栈中。以下是 Python 代码：
python
def inorder_traversal_iterative(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result
递归方法的时间复杂度和空间复杂度均为 O(n)，迭代方法的时间复杂度为 O(n)，空间复杂度平均为 O(log n)，最坏情况下为 O(n)。