二叉树中序遍历：递归与栈实现详解

中序遍历二叉树指的是按照左子树、根节点、右子树的顺序遍历二叉树。具体实现可以使用递归或者栈来实现。

递归实现

1. 如果二叉树为空，则返回。

2. 遍历二叉树的左子树。

3. 访问当前节点。

4. 遍历二叉树的右子树。

代码实现：

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

def inorderTraversal(root: TreeNode) -> List[int]:
    res = []
    def helper(node):
        if not node:
            return
        helper(node.left)
        res.append(node.val)
        helper(node.right)
    helper(root)
    return res

栈实现

1. 初始化一个栈和一个指针，指向根节点。

2. 如果当前节点不为空或者栈不为空，则执行以下操作：

   1. 将当前节点的所有左子节点入栈，并将指针指向当前节点的左子节点。

   2. 弹出栈顶元素，访问该节点，并将指针指向当前节点的右子节点。

代码实现：

def inorderTraversal(root: TreeNode) -> List[int]:
    res = []
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res