LeetCode 968二叉树监控代码困惑：DFS返回0的机制解析

首先明确你提到的三个节点状态的核心意义：

• 0：节点未被任何摄像头覆盖，必须由父节点安装摄像头来监控它
• 1：节点自身安装了摄像头，可监控自身、父节点和直接子节点
• 2：节点已被覆盖（被子节点或父节点的摄像头监控），自身无摄像头

基准情况if not root: return 2的作用 #

空节点不存在监控需求，我们将其标记为已被覆盖（状态2），这是为了避免处理叶子节点时，误将“子节点为空”判定为“需要监控”。如果空节点返回其他状态（比如0），会导致叶子节点误判需要安装摄像头，违背贪心策略——最优解是在叶子节点的父节点装摄像头，能覆盖更多节点。

为什么dfs(root.left)/dfs(root.right)会返回0？ #

当这个子节点是叶子节点时，就会返回0，具体运行过程如下：
假设当前处理的是叶子节点L，它的左右子节点都是空节点：

1. 递归调用dfs(L.left)和dfs(L.right)，因为是空节点，都返回状态2
2. 检查叶子节点L的子节点状态：两个子节点都是2（已被覆盖），但L自身没有被任何摄像头覆盖（子节点无摄像头，L自身也未安装）
3. 因此，L的状态被标记为0——这个返回值是在告诉L的父节点：“我未被覆盖，你需要装摄像头来监控我”

完整DFS逻辑的运行机制（后序遍历） #

整个DFS是从下往上处理节点（后序遍历），核心判断逻辑如下：

• 先递归获取左右子节点的状态
• 如果任意子节点状态为0（未被覆盖）：当前节点必须安装摄像头，返回状态1，同时摄像头计数+1（要覆盖这个子节点）
• 如果任意子节点状态为1（有摄像头）：当前节点已被子节点的摄像头覆盖，返回状态2
• 如果两个子节点状态都是2（都被覆盖）：当前节点未被任何摄像头覆盖，返回状态0（等待父节点安装摄像头来覆盖自己）

最后补充：如果根节点的DFS返回状态0（说明根节点未被覆盖），需要额外加1个摄像头，因为根节点没有父节点，必须自己装。

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