【LeetCode 热题 100】94. 二叉树的中序遍历——DFS

Problem: 94. 二叉树的中序遍历
题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

整体思路

这段代码旨在解决一个非常基础且经典的树遍历问题：二叉树的中序遍历 (Binary Tree Inorder Traversal)。中序遍历的顺序规则是：左子树 -> 根节点 -> 右子树。

该实现采用了一种最直观、最经典的 深度优先搜索 (DFS) 的递归方法。其核心逻辑与中序遍历的定义完全对应。

1. 主函数 inorderTraversal:

   • 这个函数是程序的入口。
   • 它首先初始化一个空的 ArrayList ans，用于存储遍历的结果。
   • 然后，它调用一个辅助的递归函数 dfs，将 ans 列表和树的根节点 root 作为参数传入，启动递归过程。
   • 最后，在 dfs 执行完毕后，返回填充好的 ans 列表。

2. 递归辅助函数 dfs:

   • 这个函数是递归的核心，它严格遵循中序遍历的“左-根-右”顺序。
   • 递归的终止条件 (Base Case)：if (node == null)。如果当前节点为 null，说明已经走到了一个叶子节点的下方，或者树本身就是空的。此时，什么也不做，直接返回，结束当前路径的探索。
   • 递归的递推关系 (Recursive Step)：
     a. 访问左子树：dfs(ans, node.left);。首先，递归地调用 dfs 函数去处理当前节点的整个左子树。这会确保在处理当前节点之前，其所有左侧的后代节点都已经被访问和记录。
     b. 访问根节点：ans.add(node.val);。在左子树全部处理完毕后，就轮到处理“根”（即当前节点 node）了。将其值 node.val 添加到结果列表 ans 中。
     c. 访问右子树：dfs(ans, node.right);。最后，递归地调用 dfs 函数去处理当前节点的整个右子树。

通过这种方式，递归调用栈的入栈和出栈过程，天然地模拟了中序遍历的访问顺序。当对一个节点的 dfs 调用结束并返回时，就意味着以它为根的整个子树已经按照中序遍历的规则被完全访问了。

完整代码

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    /**
     * 对二叉树进行中序遍历。
     * @param root 二叉树的根节点
     * @return 一个包含中序遍历结果的整数列表
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        // ans 列表用于存储最终的遍历结果。
        List<Integer> ans = new ArrayList<>();
        // 调用递归辅助函数，启动遍历过程。
        dfs(ans, root);
        return ans;
    }

    /**
     * 深度优先搜索（DFS）的递归辅助函数。
     * @param ans 结果列表，用于在递归过程中添加节点值。
     * @param node 当前正在访问的节点。
     */
    void dfs(List<Integer> ans, TreeNode node) {
        // 递归终止条件：如果当前节点为空，则返回。
        if (node == null) {
            return;
        }
        
        // 步骤 1: 递归地遍历左子树。
        dfs(ans, node.left);
        
        // 步骤 2: 访问根节点（当前节点），将其值添加到结果列表中。
        ans.add(node.val);
        
        // 步骤 3: 递归地遍历右子树。
        dfs(ans, node.right);
    }
}

时空复杂度

时间复杂度：O(N)

1. 节点访问：在整个递归过程中，每个节点都会被访问一次。当访问一个节点时，会执行一些常数时间的操作（检查是否为null，添加值到列表，进行两次递归调用）。
2. 综合分析：
   • 算法的总时间消耗与树中的节点数量 N 成正比。
   • 因此，时间复杂度为 O(N)。

空间复杂度：O(N)

1. 主要存储开销：该算法的额外空间开销主要来自两个方面：

   • 结果列表 ans：这个列表需要存储所有 N 个节点的值。在某些分析中，输出结果的空间不计入，但它确实是算法使用的内存。
   • 递归调用栈 (Call Stack)：由于使用了递归，函数调用会占用调用栈的空间。递归的深度取决于树的高度 H。

2. 递归栈深度分析：

   • 对于一个平衡二叉树，树的高度 H 约等于 log N。此时，递归栈的空间复杂度为 O(log N)。
   • 对于一个极不平衡的二叉树（例如，一个链状的树），树的高度 H 可能等于 N。此时，递归栈的空间复杂度会达到 O(N)。

综合分析：
考虑到最坏情况（一个退化的链状树），递归调用栈所需的空间可以达到 O(N)。因此，算法的空间复杂度为 O(N)。