中序遍历：递归+非递归实现

基本概念

中序遍历（Inorder Traversal） 是二叉树深度优先遍历（DFS）的一种。其访问顺序为：左子树 → 根结点 → 右子树。

对于二叉搜索树（BST），中序遍历的结果是升序序列。
递归实现直观，非递归实现需借助栈模拟系统调用过程。

算法步骤

递归版：
- 若当前结点为空，直接返回。
- 递归遍历左子树。
- 访问当前结点（如记录值）。
- 递归遍历右子树。
非递归版（栈）：
- 初始化空栈，cur 指向根结点。
- 循环直到 cur 为空且栈为空：
  - 将 cur 及其所有左孩子依次压栈（cur = cur.left）。
  - 弹出栈顶结点，访问它。
  - 将 cur 设为弹出结点的右孩子，继续循环。

内部实现

from typing import List, Optional
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
# 递归实现
def inorderTraversal_recursive(root: Optional[TreeNode]) -> List[int]:
    res = []
    
    def inorder(node):
        if not node:
            return
        inorder(node.left)       # 左
        res.append(node.val)     # 根
        inorder(node.right)      # 右
    
    inorder(root)
    return res
# 非递归实现（栈）
def inorderTraversal_iterative(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    stack = []
    cur = root
    while stack or cur:
        # 将当前结点及其所有左孩子压栈
        while cur:
            stack.append(cur)
            cur = cur.left
        # 弹出栈顶（最左结点），访问
        node = stack.pop()
        res.append(node.val)
        # 处理右子树
        cur = node.right
    return res

复杂度分析

版本	时间复杂度	空间复杂度	说明
递归	O(n)	O(h)	h 为树高，最坏 O(n)（斜树），平均 O(log n)
非递归	O(n)	O(h)	栈显式存储，最坏 O(n)

时间复杂度：每个结点恰好访问一次，O(n)。
空间复杂度：栈的最大深度等于树高，平衡树为 O(log n)，斜树为 O(n)。

应用场景

二叉搜索树（BST）的排序输出：中序遍历 BST 可得到升序序列，用于验证 BST 合法性或获取有序数据。
表达式树的中缀表达式：中序遍历表达式树（适当加括号）可还原中缀表达式。
查找第 k 小的元素：在 BST 中利用中序遍历的递增性质，可高效找到第 k 小的结点。
判断对称二叉树：中序遍历（需结合空标记）可用于辅助判断。
真实系统：
- 数据库索引（B+ 树叶子节点链表）的顺序扫描类似中序遍历思想。
- 文件系统目录的按名排序显示（先递归子目录，再显示当前？实际需具体设计）。
- 编译器符号表的顺序输出（如 dump 调试）。

中序遍历：递归+非递归实现

基本概念

算法步骤

内部实现

复杂度分析

应用场景

相关链接