DFS递归为何需保存结果而非重复调用？以二叉树摄像头题为例

在这道题的递归解法里，我们的DFS函数通常会修改树节点的状态（或依赖全局/引用传递的计数器），同时返回当前节点的状态（比如约定0=未被覆盖、1=自身有摄像头、2=已被覆盖）。不保存递归结果、重复调用dfs(curr.left)会直接导致逻辑错误，原因如下：

• 子树状态被二次修改，逻辑判断完全混乱
  第一次调用dfs(curr.left)时，已经完成了左子树的遍历处理——可能给子树里的节点添加了摄像头，或者更新了它们的覆盖状态。第二次调用时，子树的状态已经不是初始状态，再跑一遍DFS会基于被修改后的状态重新计算，导致后续的覆盖判断、摄像头部署逻辑全部出错。

• 摄像头计数被重复累加
  这类问题的核心是通过DFS遍历统计摄像头数量（一般用全局变量或引用类型变量计数）。第一次调用dfs(curr.left)已经完成左子树的摄像头部署和计数，第二次调用会再次遍历左子树，重复执行摄像头部署逻辑，导致计数远超正确值，最终结果自然无法通过测试。

举个直观的例子：假设左子树是一个叶子节点，第一次调用dfs会返回状态0（未被覆盖），此时父节点会决定安装摄像头（计数+1）。如果第二次再调用dfs(curr.left)，这个叶子节点已经被父节点的摄像头覆盖，状态变成2，此时逻辑会误判它不需要任何处理，导致后续的父节点、祖父节点的状态判断全部偏离正确路径；如果计数逻辑在子树内部，还会重复累加摄像头数量。

本质上，这道题的DFS过程是带有副作用的（修改状态或计数），不能对同一个子树重复执行。必须把第一次执行得到的子树状态保存下来，供当前节点的逻辑判断使用，而不能通过再次调用DFS去获取状态。

内容的提问来源于stack exchange，提问作者srm26