DFS 精通指南：何时使用全局变量 vs 返回值 - 完整面试攻略

引言：面试中的关键决策

DFS（深度优先搜索）中最让面试者困惑的问题之一是：

我应该使用全局变量，还是通过返回值来解决？

这不仅仅是代码风格的选择——而是顶级面试官评估的基本模式识别能力。做出错误的选择会导致：

• ❌ 代码复杂难以调试
• ❌ 因为 Java 的按值传递陷阱导致错误答案
• ❌ 面试官问”能简化一下吗？”

在微软、Booking.com 和阿里巴巴的 11 年以上经验中，我见过这个问题难倒很多优秀的候选人。本指南为你提供清晰的决策框架和可复用的模板。

---

核心区别

🌍 全局变量（类级别状态）

使用场景：需要跨多个分支累积信息或跟踪超越当前子树的状态。

    Root
   /    \
  A      B
 / \    / \
C   D  E   F

目标：统计所有值 > 阈值的节点
→ 需要累积：C ✓, A ✗, D ✓, ... → 总计：4
   这个计数跨越整棵树 → 全局变量

🔄 返回值（局部计算）

使用场景：节点的结果可以从其子节点的结果计算得出并向上返回。

    Root(4)
   /       \
  A(2)     B(6)
 / \       / \
C(1) D(3) E(5) F(7)

目标：找到树中的最大值
→ A 的最大值 = max(C, D) = 3
→ B 的最大值 = max(E, F) = 7
→ Root 的最大值 = max(A, B) = 7
   每个节点向父节点返回一个值 → 返回值

---

模式 1：何时必须使用全局变量

特征

1. 累积来自多个独立路径的结果
2. 在中序/前序/后序遍历中跟踪状态
3. 跨分支进行计数、收集或比较
4. 需要维护”前一个”或”目前最佳”状态

经典问题：二叉搜索树的最小绝对差

问题 1：二叉搜索树的最小绝对差 (LC 530)

题目：给定一个 BST，找出任意两个节点之间的最小绝对差。

为什么要用全局变量？
你需要在中序遍历期间跟踪前一个节点：

BST:      4
        /   \
       2     6
      / \
     1   3

中序遍历：1 → 2 → 3 → 4 → 6
          ↑   ↑
       prev curr → diff = 2-1 = 1 (最小！)

"prev" 必须在递归调用之间持久存在 → 全局变量

模板：Java（全局变量模式）

class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private Integer prev = null;  // 中序遍历中的前一个节点值
    
    public int getMinimumDifference(TreeNode root) {
        inorderDFS(root);
        return minDiff;
    }
    
    private void inorderDFS(TreeNode node) {
        if (node == null) return;
        
        inorderDFS(node.left);  // 访问左子树
        
        // 处理当前节点
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;  // 更新全局 prev
        
        inorderDFS(node.right);  // 访问右子树
    }
}

模板：Python（全局变量模式）

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        self.min_diff = float('inf')
        self.prev = None
        
        def inorder_dfs(node):
            if not node:
                return
            
            inorder_dfs(node.left)
            
            # 处理当前节点
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val
            
            inorder_dfs(node.right)
        
        inorder_dfs(root)
        return self.min_diff

模板：JavaScript（全局变量模式）

var getMinimumDifference = function(root) {
    let minDiff = Infinity;
    let prev = null;
    
    function inorderDFS(node) {
        if (!node) return;
        
        inorderDFS(node.left);
        
        // 处理当前节点
        if (prev !== null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;
        
        inorderDFS(node.right);
    }
    
    inorderDFS(root);
    return minDiff;
};

复杂度：

• 时间：$O(n)$ - 访问每个节点一次
• 空间：$O(h)$ - 递归栈高度

为什么返回值在这里不起作用

常见错误：

// ❌ 错误：尝试将 prev 作为参数传递
private void dfs(TreeNode node, int prev) {
    if (node == null) return;
    dfs(node.left, prev);
    minDiff = Math.min(minDiff, node.val - prev);
    prev = node.val;  // ❌ 这不会传播！（按值传递）
    dfs(node.right, prev);
}

为什么失败：在 Java 中，int 是按值传递的。当你更新 prev = node.val 时，它只影响局部副本。下一次递归调用仍然看到旧值。

---

进阶示例：有序链表转换二叉搜索树（中序遍历模拟）

问题 2：有序链表转换二叉搜索树 (LC 109)

题目：给定一个单链表，其中的元素按升序排列，将其转换为一棵高度平衡的二叉搜索树。

为什么要用全局变量？
最优解使用了一个巧妙的思路：模拟 BST 中序遍历的同时按顺序消费有序链表。

链表：-10 → -3 → 0 → 5 → 9
索引：  0    1   2   3   4

BST 中序遍历：左子树 → 根 → 右子树
链表顺序：    顺序消费

关键洞察：BST 的中序遍历产生有序序列！
→ 我们可以按中序方式构建树，同时移动链表指针

挑战：
与数组不同，我们无法在 O(1) 时间内随机访问链表的”中间”节点。但我们可以：

1. 计算链表长度：O(n)
2. 使用索引范围来确定树的结构
3. 使用全局指针按中序顺序消费链表节点

可视化：

为索引 [0, 4] 构建 BST，mid = 2

步骤 1：构建左子树 [0, 1]
  ├─ [0, 1]，mid = 0
  │  ├─ [0, -1] → null
  │  ├─ 创建节点(-10) ← current 指向这里，移动到 -3
  │  └─ [1, 1]，mid = 1
  │     ├─ [1, 0] → null
  │     ├─ 创建节点(-3) ← current 指向这里，移动到 0
  │     └─ [2, 1] → null

步骤 2：创建根节点(0) ← current 指向这里，移动到 5

步骤 3：构建右子树 [3, 4]
  └─ 类似过程...

'current' 指针必须在所有递归调用之间持久存在！

模板：Java（中序遍历 + 全局指针）

class Solution {
    private ListNode current;  // 全局变量：跟踪链表当前位置
    
    public TreeNode sortedListToBST(ListNode head) {
        // 步骤 1：计算链表长度
        int size = getSize(head);
        
        // 步骤 2：初始化全局指针
        current = head;
        
        // 步骤 3：使用中序遍历模式构建 BST
        return inorderBuild(0, size - 1);
    }
    
    private int getSize(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }
    
    /**
     * 为索引范围 [left, right] 构建 BST，使用中序遍历
     * 关键：按中序顺序处理节点（左子树 → 根 → 右子树）
     */
    private TreeNode inorderBuild(int left, int right) {
        if (left > right) {
            return null;
        }
        
        int mid = left + (right - left) / 2;
        
        // 中序步骤 1：先构建左子树
        // 这会按有序方式消费链表节点
        TreeNode leftChild = inorderBuild(left, mid - 1);
        
        // 中序步骤 2：处理当前节点（此子树的根）
        TreeNode root = new TreeNode(current.val);
        root.left = leftChild;
        current = current.next;  // ⭐ 向前移动全局指针
        
        // 中序步骤 3：最后构建右子树
        root.right = inorderBuild(mid + 1, right);
        
        return root;
    }
}

模板：Python（中序遍历 + 全局指针）

class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        # 步骤 1：计算链表长度
        size = self.get_size(head)
        
        # 步骤 2：初始化全局指针
        self.current = head
        
        # 步骤 3：使用中序遍历构建 BST
        return self.inorder_build(0, size - 1)
    
    def get_size(self, head: ListNode) -> int:
        size = 0
        while head:
            size += 1
            head = head.next
        return size
    
    def inorder_build(self, left: int, right: int) -> TreeNode:
        if left > right:
            return None
        
        mid = (left + right) // 2
        
        # 中序：左子树 → 根 → 右子树
        left_child = self.inorder_build(left, mid - 1)
        
        # 处理当前节点
        root = TreeNode(self.current.val)
        root.left = left_child
        self.current = self.current.next  # 移动指针
        
        root.right = self.inorder_build(mid + 1, right)
        
        return root

模板：JavaScript（中序遍历 + 全局指针）

var sortedListToBST = function(head) {
    // 步骤 1：计算链表长度
    const getSize = (node) => {
        let size = 0;
        while (node) {
            size++;
            node = node.next;
        }
        return size;
    };
    
    const size = getSize(head);
    let current = head;  // 闭包捕获此变量
    
    // 步骤 2：使用中序遍历构建 BST
    const inorderBuild = (left, right) => {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        
        // 中序：左子树 → 根 → 右子树
        const leftChild = inorderBuild(left, mid - 1);
        
        // 处理当前节点
        const root = new TreeNode(current.val);
        root.left = leftChild;
        current = current.next;  // 向前移动指针
        
        root.right = inorderBuild(mid + 1, right);
        
        return root;
    };
    
    return inorderBuild(0, size - 1);
};

复杂度：

• 时间：$O(n)$ - 每个链表节点恰好处理一次
• 空间：$O(\log n)$ - 平衡树的递归栈

深入理解：为什么这样有效

中序遍历的魔力：

1. BST 性质：BST 的中序遍历产生有序序列

   BST:      4          中序：[2, 4, 6]
           /   \                ↑  ↑  ↑
          2     6       有序：匹配链表！

2. 逆向思维：如果我们按中序顺序构建树，就可以顺序消费有序链表

   链表指针移动：-10 → -3 → 0 → 5 → 9
   树的构建：    左子树 → 根 → 右子树
               (消费 -10,-3) (0)  (消费 5,9)

3. 索引范围技巧：我们使用 [left, right] 索引来确定树的结构，无需遍历链表查找中点

   范围 [0, 4]，mid = 2 → 根节点将是第 3 个节点（索引 2）
   先构建左边 [0, 1] → 消费索引 0、1 的节点
   然后创建根 → 消费索引 2 的节点
   最后构建右边 [3, 4] → 消费索引 3、4 的节点

为什么全局变量在这里是必需的

如果尝试将 current 作为参数传递会怎样？

// ❌ 错误：尝试将 current 作为参数传递
private TreeNode build(int left, int right, ListNode current) {
    if (left > right) return null;
    
    int mid = (left + right) / 2;
    TreeNode leftChild = build(left, mid - 1, current);  // ❌
    
    TreeNode root = new TreeNode(current.val);
    current = current.next;  // ❌ 只更新局部副本！
    
    TreeNode rightChild = build(mid + 1, right, current);  // ❌ 错误的节点！
    return root;
}

为什么失败：

1. Java 按值传递对象引用
2. 当你执行 current = current.next 时，你更新的是局部引用，而不是原始引用
3. 从 build(left, mid - 1, current) 返回后，外部作用域仍然看到旧的 current
4. 右子树会从链表中读取错误的节点

修复方法：使用类级别变量，让所有递归调用共享：

// ✅ 正确：类级别变量
private ListNode current;

private TreeNode build(int left, int right) {
    // 所有调用修改同一个 current 指针
    current = current.next;  // ✅ 在所有调用之间持久存在
}

其他方法对比

方法 1：快慢指针（O(n log n) 时间）

// 每次通过遍历链表找到中点
private ListNode findMiddle(ListNode head) {
    ListNode slow = head, fast = head, prev = null;
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    if (prev != null) prev.next = null;  // 分割链表
    return slow;
}
// 递归构建：每层 O(n) × O(log n) 层 = O(n log n)

方法 2：转换为数组（O(n) 时间，O(n) 空间）

// 将链表复制到数组，然后从数组构建 BST
int[] arr = new int[size];
// 需要额外 O(n) 空间

我们的方法：中序模拟 ⭐ 最佳时空复杂度

• 时间：O(n) - 单次遍历链表
• 空间：O(log n) - 仅递归栈
• 巧妙利用有序性质！

何时使用此模式

“中序模拟 + 全局指针”模式适用于：

1. ✅ 输入是顺序数据结构（链表、流）
2. ✅ 输出遵循遍历顺序（中序、前序等）
3. ✅ 需要顺序消费输入同时构建结构
4. ✅ 随机访问成本高或不可能

类似问题：

• 根据前序遍历构造 BST（LC 1008）
• 序列化和反序列化 BST（LC 449）
• 从中序和前序构造树（LC 105）

---

模式 2：何时返回值更好

特征

1. 自下而上计算属性（从叶子到根）
2. 每个节点的结果仅取决于其子节点
3. 不需要跨兄弟分支跟踪状态
4. 树的属性：高度、最大值、总和等

经典问题：二叉树的最大深度

问题 2：二叉树的最大深度 (LC 104)

题目：找出二叉树的最大深度（高度）。

为什么用返回值？
每个节点的深度 = 1 + max(左子树深度, 右子树深度)。

树:       3
        /   \
       9    20
           /  \
          15   7

Depth(15) = 1 (叶子)
Depth(7)  = 1 (叶子)
Depth(20) = 1 + max(1, 1) = 2
Depth(9)  = 1 (叶子)
Depth(3)  = 1 + max(1, 2) = 3 ✓

每个节点从子节点计算 → 返回值

模板：Java（返回值模式）

class Solution {
    public int maxDepth(TreeNode root) {
        // 基本情况
        if (root == null) {
            return 0;
        }
        
        // 递归情况：从子节点计算
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        
        // 组合并返回
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

模板：Python（返回值模式）

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # 基本情况
        if not root:
            return 0
        
        # 递归情况：从子节点计算
        left_depth = self.maxDepth(root.left)
        right_depth = self.maxDepth(root.right)
        
        # 组合并返回
        return 1 + max(left_depth, right_depth)

模板：JavaScript（返回值模式）

var maxDepth = function(root) {
    // 基本情况
    if (!root) return 0;
    
    // 递归情况：从子节点计算
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    // 组合并返回
    return 1 + Math.max(leftDepth, rightDepth);
};

复杂度：

• 时间：$O(n)$ - 访问每个节点一次
• 空间：$O(h)$ - 递归栈高度

---

模式 3：混合方法（全局 + 返回值）

有些问题需要同时使用两种模式！

示例：二叉树中的最大路径和

问题 3：二叉树中的最大路径和 (LC 124)

题目：找出二叉树中的最大路径和。路径可以从任意节点开始和结束。

为什么用混合方式？

• 全局变量：跟踪整体最大路径和（可以经过任意节点）
• 返回值：对于每个节点，返回最大单路径和（可以被父节点扩展）

树:      -10
        /    \
       9     20
            /  \
           15   7

可能的路径：
- 15 → 20 → 7 (和 = 42) ← 最大！（存储在全局变量中）
- 9 单独 (和 = 9)
- 15 → 20 (和 = 35)

但当我们返回到父节点 (-10) 时：
- 左子树返回：9
- 右子树返回：35 (20 + max(15, 7))
- 我们用以下值更新全局最大值：9 + (-10) + 35 = 34

模板：Java（混合模式）

class Solution {
    private int maxSum = Integer.MIN_VALUE;  // 全局：整体最大值
    
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }
    
    private int maxGain(TreeNode node) {
        if (node == null) return 0;
        
        // 返回值：从子节点获得的最大单路径收益
        int leftGain = Math.max(maxGain(node.left), 0);  // 忽略负路径
        int rightGain = Math.max(maxGain(node.right), 0);
        
        // 全局更新：经过当前节点的路径
        int pathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThroughNode);
        
        // 返回：最佳单路径（不能同时使用两个子节点）
        return node.val + Math.max(leftGain, rightGain);
    }
}

模板：Python（混合模式）

class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_sum = float('-inf')
        
        def max_gain(node):
            if not node:
                return 0
            
            # 返回值：最大单路径收益
            left_gain = max(max_gain(node.left), 0)
            right_gain = max(max_gain(node.right), 0)
            
            # 全局更新：经过当前节点的路径
            path_through_node = node.val + left_gain + right_gain
            self.max_sum = max(self.max_sum, path_through_node)
            
            # 返回：最佳单路径
            return node.val + max(left_gain, right_gain)
        
        max_gain(root)
        return self.max_sum

模板：JavaScript（混合模式）

var maxPathSum = function(root) {
    let maxSum = -Infinity;
    
    function maxGain(node) {
        if (!node) return 0;
        
        // 返回值：最大单路径收益
        const leftGain = Math.max(maxGain(node.left), 0);
        const rightGain = Math.max(maxGain(node.right), 0);
        
        // 全局更新：经过当前节点的路径
        const pathThroughNode = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, pathThroughNode);
        
        // 返回：最佳单路径
        return node.val + Math.max(leftGain, rightGain);
    }
    
    maxGain(root);
    return maxSum;
};

复杂度：

• 时间：$O(n)$
• 空间：$O(h)$

关键见解：

• 全局变量存储”树中任意位置的最佳路径”（可以同时使用左右两个子节点）
• 返回值表示”向上延伸的最佳路径”（只能使用一个子节点）

---

决策框架：快速参考

使用全局变量的场景：

✅ 跟踪整个遍历过程中的”前一个”或”目前最佳”
✅ 从多个分支累积结果（计数、总和、列表）
✅ 中序/前序遍历中顺序很重要
✅ 比较不同子树中的节点
✅ 需要维护在递归返回后仍然存在的状态

示例：

• BST 中序遍历问题（第 k 小元素，验证 BST）
• 路径总和收集（所有总和为目标的路径）
• 统计满足全局条件的节点
• 序列化/反序列化树

使用返回值的场景：

✅ 自下而上从子节点计算属性
✅ 父节点的结果仅取决于子节点的结果
✅ 不需要跨兄弟分支进行比较
✅ 树结构属性（高度、直径、平衡）
✅ 可以表示为：result = combine(left_result, right_result)

示例：

• 树的高度/深度
• 节点值的总和
• 检查树是否平衡
• 最近公共祖先（使用特定的返回值编码）

同时使用两者的场景：

✅ 需要跟踪全局最优值同时计算局部属性
✅ 在每一层有不同的度量（全局最大值 vs 局部贡献）

示例：

• 最大路径和（任意路径）
• 树的直径（任意两个节点之间的最长路径）
• 节点和祖先之间的最大差值

---

常见陷阱及如何避免

陷阱 1：使用基本类型参数作为”全局”状态（Java）

// ❌ 错误：prev 不会在调用之间持久存在
private void dfs(TreeNode node, int prev) {
    // ...
    prev = node.val;  // 只更新局部副本！
    dfs(node.right, prev);
}

修复：使用类级别变量或包装类：

// ✅ 正确：使用 Integer[] 或类字段
private Integer prev = null;

// 或使用数组作为可变引用
private void dfs(TreeNode node, int[] prev) {
    prev[0] = node.val;  // 修改数组内容
}

陷阱 2：过度使用全局变量

// ❌ 不好：对简单的树高度使用全局变量
private int maxDepth = 0;

public int maxDepth(TreeNode root) {
    dfs(root, 0);
    return maxDepth;
}

private void dfs(TreeNode node, int depth) {
    if (node == null) {
        maxDepth = Math.max(maxDepth, depth);
        return;
    }
    dfs(node.left, depth + 1);
    dfs(node.right, depth + 1);
}

修复：使用返回值使代码更清晰：

// ✅ 更好：返回值更清晰
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

陷阱 3：忘记重置全局变量

class Solution {
    private int count = 0;  // ❌ 在测试用例之间持久存在！
    
    public int countNodes(TreeNode root) {
        dfs(root);
        return count;
    }
}

修复：始终在公共方法中重置：

public int countNodes(TreeNode root) {
    count = 0;  // ✅ 每次调用前重置
    dfs(root);
    return count;
}

---

面试策略：面试官的期望

1. 提出澄清问题

在编码前，说明你的方法：

“我注意到这个问题需要跟踪所有节点的最小值。我将使用类级别变量在 DFS 期间累积结果。这样可以吗？“

2. 解释权衡

当被问到”能避免使用全局变量吗？”：

• 如果可以：解释替代方案（返回值模式）
• 如果不可以：解释原因（例如，“我们需要跨兄弟分支跟踪状态”）

3. 代码简洁

• 清楚地初始化全局变量
• 添加注释解释返回值代表什么
• 变量命名要有描述性（prevNodeVal，而不是 x）

4. 测试边缘情况

• 空树（null root）
• 单节点
• 倾斜树（全部向左或全部向右）
• 负值（如果适用）

---

练习题目

全局变量模式

1. LC 98：验证二叉搜索树
2. LC 109：有序链表转换二叉搜索树 ⭐（中序模拟模式）
3. LC 230：二叉搜索树中第 K 小的元素
4. LC 257：二叉树的所有路径
5. LC 129：求根节点到叶节点数字之和

返回值模式

1. LC 110：平衡二叉树
2. LC 543：二叉树的直径
3. LC 236：二叉树的最近公共祖先
4. LC 404：左叶子之和

混合模式

1. LC 124：二叉树中的最大路径和
2. LC 1026：节点与其祖先之间的最大差值

---

总结：你的面试备忘单

指标	使用全局变量	使用返回值
状态范围	跨整棵树	仅在子树内
遍历顺序重要	✅ 是（中序等）	❌ 否
比较兄弟节点	✅ 是	❌ 否
跟踪”前一个”节点	✅ 是	❌ 否
自下而上计算	❌ 否	✅ 是
树属性（高度、总和）	❌ 否	✅ 是
累积结果	✅ 是	使用返回值 + 组合

面试最后提示

如果不确定，从返回值开始（更简洁，更容易推理）。如果发现需要”记住”前一个节点或兄弟分支的某些内容，切换到全局变量。

掌握了这些模式，你将能自信地处理 80% 以上的树 DFS 面试问题！🚀