Open youngyangyang04 opened 3 months ago
我发现情况2和情况3的顺序不能交换,否则代码无法通过
private int traversal(TreeNode node) {
if (node == null) return 1; // 空节点
int left = traversal(node.left);
int right = traversal(node.right);
if (left == 0 || right == 0) { // 存在孩子未被监控, 安装
count++;
return 2;
}
if (left == 1 && right == 1) { // 孩子都被孙子监控, 不安装
return 0;
}
return 1; // 已被孩子监控
}
// 例: [0,0,null,0,null,0,null,null,0], count = 0
深度5: left = 1, right = 1(叶节点,无需监控), 返回 0(不安装)
深度4: left = 1, right = 0(存在孩子未被监控), 返回 2(安装), count = 1
深度3: left = 2, right = 1(存在孩子是摄像头), 返回 1(已被孩子监控)
深度2: left = 1, right = 1(孩子都被孙子监控), 返回 0(不安装)
深度1: left = 0, right = 1(存在孩子未被监控), 返回 2(安装), count = 2
// 注: 在第 1、4 层,第 2、4 层,第 2、5 层安装摄像头,都是正确方案。
@yuyuanyuanhua
我发现情况2和情况3的顺序不能交换,否则代码无法通过
是吧 因为比如说左节点是无覆盖,右节点是摄像头,父节点还是必须要是摄像头
https://www.programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html