给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例1
输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
示例2
输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
抛砖引玉
遍历二叉树安装摄像头(X),且可被该摄像头监控到的节点标记(Y),未受该节点和其他监控节点监控的节点标记(Z)
递归遍历二叉树:
递归时从叶子节点开始标记节点被监控的状态,那么在遍历过程中遇到的二叉子树都可以看成有一个'根节点'和左右子树组成:
3 X Y X
/ \ -> / \ / \ / \
9 20 Y Y Y X Y Z
对应每个遍历到的'根节点'和左右子树组,都可能包含下面情况:
var minCameraCover = function(root) {
let _result = 0
// 递归到二叉树根节点如果其不能被子树的X监控需要在增加一个X
if (dfs(root) === 'Z') _result = _result + 1
function dfs(node) {
// 默认叶子节点不放置X,让其受其他节点监控
if (node == null) return 'Y'
let left = dfs(node.left),
right = dfs(node.right)
// 1. 如果左右节点都是Y,则根节点只能放置X
if (left == 'Y' && right == 'Y') return 'Z'
// 2. 如果左右节点中有1个或者2个X,那么根节点自动变成Y(注意此时左右节点不能有未受其他节点影响的子节点)
if (left !== 'Z' && right !== 'Z' && (left === 'X' || right === 'X')) {
return 'Y'
}
// 3. 如果左右节点均为查询到安装X和被监控Y,则在根节点放置X
_result++
return 'X'
}
return _result
}
对于每个节点 root ,需要维护三种类型的状态:
设其左右孩子 left, right,对应的状态变量分别为(
,
,
)、(
,
,
):
+
+ 1;
+
,
+
)
因为定义 c 是 root 的右子树又被拆分左右子树,则 b 逻辑上是大于等于 c 的,a 包含了左右子树的
、
的情况则逻辑上是大于等于 b 的则:
覆盖当前子树:
+ 覆盖整个右子树摄像头数
+ 覆盖整个右子树的左右子树的摄像头数
(因为
包含了 root 放置的情况,所有根节点可能重复放置所有该组合一定大于上一组)
+ 右节子树根节点放置摄像头形成全覆盖
+ 右节子树根节点放置摄像头形成全覆盖
+ 右节子树形成全覆盖,但不一定是右子树根节点放置摄像头
+ 右节子树形成全覆盖,但不一定是右子树根节点放置摄像头
+ 1
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minCameraCover = function(root) {
function dfs(root) {
if (!root) {
return [Math.floor(Number.MAX_SAFE_INTEGER / 2), 0, 0]
}
const [la, lb, lc] = dfs(root.left)
const [ra, rb, rc] = dfs(root.right)
const a = lc + rc + 1
const b = Math.min(a, la + rb, lb + ra, la + ra, lb + rb + 1)
const c = Math.min(a, lb + rb)
return [a, b, c]
}
return dfs(root)[1]
}