LeetCode 热题 100 94. 二叉树的中序遍历

LeetCode 热题 100 | 94. 二叉树的中序遍历

大家好，今天我们来解决一道经典的算法题——二叉树的中序遍历。这道题在 LeetCode 上被标记为简单难度，要求我们给定一个二叉树的根节点 root，返回它的中序遍历结果。下面我将详细讲解解题思路，并附上 Python 代码实现。

题目描述

给定一个二叉树的根节点 root，返回它的中序遍历结果。

示例：

输入：root = [1,null,2,3]
输出：[1,3,2]

解题思路

中序遍历是二叉树遍历的一种方式，遍历顺序为：左子树 -> 根节点 -> 右子树。我们可以通过递归或迭代的方式来实现中序遍历。

核心思想

1. 递归法：

   • 递归地遍历左子树。
   • 访问根节点。
   • 递归地遍历右子树。

2. 迭代法：

   • 使用栈来模拟递归过程。
   • 从根节点开始，将所有左子节点入栈，直到没有左子节点。
   • 弹出栈顶节点，访问该节点，然后转向其右子节点。

代码实现

方法 1：递归法

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

def inorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    result = []  # 用于存储遍历结果
    
    def inorder(node):
        if not node:
            return
        # 递归遍历左子树
        inorder(node.left)
        # 访问根节点
        result.append(node.val)
        # 递归遍历右子树
        inorder(node.right)
    
    inorder(root)  # 从根节点开始遍历
    return result

方法 2：迭代法

def inorderTraversal(root):
    """
    :type root: TreeNode
    :rtype: List[int]
    """
    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

代码解析

递归法

1. 定义递归函数 inorder：

   • 如果当前节点为空，则返回。
   • 递归遍历左子树。
   • 访问根节点，将其值加入结果列表。
   • 递归遍历右子树。

2. 调用递归函数：

   • 从根节点开始遍历。

迭代法

1. 初始化：

   • result 用于存储遍历结果。
   • stack 用于模拟递归的栈。
   • current 指向当前节点。

2. 遍历过程：

   • 将所有左子节点入栈，直到没有左子节点。
   • 弹出栈顶节点并访问，将其值加入结果列表。
   • 转向右子节点，继续遍历。

复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
• 空间复杂度：
  • 递归法：O(n)，递归调用栈的深度为树的高度。
  • 迭代法：O(n)，栈的最大空间为树的高度。

示例运行

示例 1

# 创建二叉树 [1,null,2,3]
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

# 中序遍历
print(inorderTraversal(root))  # 输出: [1, 3, 2]

示例 2

# 创建空二叉树 []
root = None

# 中序遍历
print(inorderTraversal(root))  # 输出: []

示例 3

# 创建二叉树 [1]
root = TreeNode(1)

# 中序遍历
print(inorderTraversal(root))  # 输出: [1]

总结

通过递归或迭代的方式，我们可以高效地实现二叉树的中序遍历。递归法代码简洁，但可能受递归深度限制；迭代法使用栈模拟递归过程，适合处理较大的树。希望这篇题解对你有帮助！如果还有其他问题，欢迎继续提问！

关注我，获取更多算法题解和编程技巧！