94. 二叉树的中序遍历

题目链接：94. 二叉树的中序遍历

题目描述

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

核心思考：深度优先搜索 (DFS)

二叉树的中序遍历遵循 “左 -> 根 -> 右” 的顺序。这是深度优先搜索 (DFS) 的一种经典应用。

1. 递归逻辑：当访问到一个节点时，首先递归地处理其左子树，然后记录当前节点的值，最后递归地处理其右子树。
2. 基准情形：如果当前节点为空，则直接返回，不进行任何处理。

虽然遍历问题也可以使用栈来模拟迭代过程，但递归写法非常直观且易于理解，是解决树问题的首选方案。

解题思路 (Python)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []
        def dfs(node):
            if node == None:
                return
            dfs(node.left)
            ans.append(node.val)
            dfs(node.right)
        dfs(root)
        return ans

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树的节点数。每个节点被访问且处理且仅处理一次。
• 空间复杂度：O(H)，其中 H 是树的高度。主要由递归调用的栈空间产生。平均情况下高度平衡的树空间为 O(log N)，最坏情况（退化为链状）下为 O(N)。