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)。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

val1 val2 val3 ... valN

输入一行整数数组表示二叉树的层序遍历，None 表示空节点。

完整代码：

import sys

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

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    queue = [root]
    i = 1
    while queue and i < len(arr):
        node = queue.pop(0)
        if arr[i] is not None:
            node.left = TreeNode(arr[i])
            queue.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            queue.append(node.right)
        i += 1
    return root

def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    while result and result[-1] is None:
        result.pop()
    return result

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

def main():
    arr = sys.stdin.read().strip().split()
    tree_arr = [None if v == 'None' else int(v) for v in arr]
    root = build_tree(tree_arr)

    sol = Solution()
    result = sol.inorderTraversal(root)
    print(result)

if __name__ == "__main__":
    main()