968. 监控二叉树

题目描述

输入一棵二叉树的根节点 root，树用层序数组表示，所有节点的值都是 0。

可以在节点上放摄像头。一个摄像头能覆盖它所在的节点、它的父节点和它的直接子节点。

返回让树中每个节点都被至少一个摄像头覆盖所需的最少摄像头数。

示例 1

输入：root = [0,0,null,0,0]
输出：1

解释：在根的左孩子上放一个，就能覆盖全部四个节点。

示例 2

输入：root = [0,0,null,0,null,0,null,null,0]
输出：2

解释：这是一条长链，一个摄像头覆盖不完，至少需要两个。

数据范围

节点数在 [1, 1000] 范围内。
每个节点的值都为 0。

解题思路：后序遍历 + 贪心

贪心 + 后序遍历。叶子上装摄像头很浪费，不如装在叶子的父节点上，还能顺带看到更多节点。每个节点向上报告三种状态：0 = 没被监控，1 = 装了摄像头，2 = 已被监控但没装。空节点视为 2。若有孩子是 0，当前节点必须装；否则若有孩子是 1，当前已被监控；否则当前没被监控，留给父节点处理。最后根若仍是 0，再补一个。

为什么正确

dfs(x) 返回后，x 的所有后代都已被监控，且用到的摄像头数最少；x 自己可能还在等父节点来监控（状态 0）。

复杂度分析

时间 O(n)，空间 O(h)。

易错点

忘记最后检查根：根没有父节点，若它返回 0 必须补装一个；另外空节点要返回 2（已监控），返回 0 会导致在叶子上装。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        self.cams = 0
        def dfs(node):
            if node is None:
                return 2
            left = dfs(node.left)
            right = dfs(node.right)
            if left == 0 or right == 0:
                self.cams += 1
                return 1
            if left == 1 or right == 1:
                return 2
            return 0
        if dfs(root) == 0:
            self.cams += 1
        return self.cams

class Solution {
    int cams = 0;

    int dfs(TreeNode node) {
        if (node == null) {
            return 2;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        if (left == 0 || right == 0) {
            cams++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return 0;
    }

    public int minCameraCover(TreeNode root) {
        cams = 0;
        if (dfs(root) == 0) {
            cams++;
        }
        return cams;
    }
}

class Solution {
public:
    int cams = 0;
    int dfs(TreeNode* node) {
        if (node == nullptr) {
            return 2;
        }
        int left = dfs(node->left);
        int right = dfs(node->right);
        if (left == 0 || right == 0) {
            cams++;
            return 1;
        }
        if (left == 1 || right == 1) {
            return 2;
        }
        return 0;
    }
    int minCameraCover(TreeNode* root) {
        cams = 0;
        if (dfs(root) == 0) {
            cams++;
        }
        return cams;
    }
};

func minCameraCover(root *TreeNode) int {
	cams := 0
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 2
		}
		left := dfs(node.Left)
		right := dfs(node.Right)
		if left == 0 || right == 0 {
			cams++
			return 1
		}
		if left == 1 || right == 1 {
			return 2
		}
		return 0
	}
	if dfs(root) == 0 {
		cams++
	}
	return cams
}

var minCameraCover = function(root) {
    let cams = 0;
    const dfs = (node) => {
        if (node === null) {
            return 2;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left === 0 || right === 0) {
            cams++;
            return 1;
        }
        if (left === 1 || right === 1) {
            return 2;
        }
        return 0;
    };
    if (dfs(root) === 0) {
        cams++;
    }
    return cams;
};

function minCameraCover(root: TreeNode | null): number {
    let cams = 0;
    const dfs = (node: TreeNode | null): number => {
        if (node === null) {
            return 2;
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        if (left === 0 || right === 0) {
            cams++;
            return 1;
        }
        if (left === 1 || right === 1) {
            return 2;
        }
        return 0;
    };
    if (dfs(root) === 0) {
        cams++;
    }
    return cams;
}

载入编辑器，自己跑一遍 →

其他解法

贪心解法只传递一个状态，代码更短；树形动态规划传递三个状态，正确性更容易说明，也更容易推广。

解法 2：三状态树形动态规划时间 O(n)，空间 O(n)

对每个节点返回三个值：a 是该节点放摄像头且子树全覆盖的最少摄像头数；b 是子树全覆盖的最少数；c 是除该节点本身外子树全覆盖的最少数。空节点返回 (∞, 0, 0)。转移为 a = lc + rc + 1，b = min(a, la + rb, ra + lb)，c = min(a, lb + rb)，答案是根的 b。

不依赖贪心正确性的证明，状态转移可以直接推导。同样的框架可以推广到带权摄像头等变形，贪心就不再适用。

import sys

class Solution:
    def minCameraCover(self, root: Optional[TreeNode]) -> int:
        sys.setrecursionlimit(10000)
        INF = 10 ** 8

        def dfs(node):
            if node is None:
                return INF, 0, 0
            la, lb, lc = dfs(node.left)
            ra, rb, rc = dfs(node.right)
            a = lc + rc + 1
            b = min(a, la + rb, ra + lb)
            c = min(a, lb + rb)
            return a, b, c

        return dfs(root)[1]

class Solution {
    static final int INF = 100000000;

    int[] dfs(TreeNode node) {
        if (node == null) return new int[]{INF, 0, 0};
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int a = l[2] + r[2] + 1;
        int b = Math.min(a, Math.min(l[0] + r[1], r[0] + l[1]));
        int c = Math.min(a, l[1] + r[1]);
        return new int[]{a, b, c};
    }

    public int minCameraCover(TreeNode root) {
        return dfs(root)[1];
    }
}

class Solution {
public:
    const int INF = 100000000;

    array<int, 3> dfs(TreeNode* node) {
        if (node == nullptr) return {INF, 0, 0};
        auto l = dfs(node->left);
        auto r = dfs(node->right);
        int a = l[2] + r[2] + 1;
        int b = min(a, min(l[0] + r[1], r[0] + l[1]));
        int c = min(a, l[1] + r[1]);
        return {a, b, c};
    }

    int minCameraCover(TreeNode* root) {
        return dfs(root)[1];
    }
};

func minCameraCover(root *TreeNode) int {
	const INF = 100000000
	var dfs func(node *TreeNode) (int, int, int)
	dfs = func(node *TreeNode) (int, int, int) {
		if node == nil {
			return INF, 0, 0
		}
		la, lb, lc := dfs(node.Left)
		ra, rb, rc := dfs(node.Right)
		a := lc + rc + 1
		b := min(a, la+rb, ra+lb)
		c := min(a, lb+rb)
		return a, b, c
	}
	_, b, _ := dfs(root)
	return b
}

var minCameraCover = function(root) {
    const INF = 1e8;
    const dfs = (node) => {
        if (node === null) return [INF, 0, 0];
        const [la, lb, lc] = dfs(node.left);
        const [ra, rb, rc] = dfs(node.right);
        const a = lc + rc + 1;
        const b = Math.min(a, la + rb, ra + lb);
        const c = Math.min(a, lb + rb);
        return [a, b, c];
    };
    return dfs(root)[1];
};

function minCameraCover(root: TreeNode | null): number {
    const INF = 1e8;
    const dfs = (node: TreeNode | null): [number, number, number] => {
        if (node === null) return [INF, 0, 0];
        const [la, lb, lc] = dfs(node.left);
        const [ra, rb, rc] = dfs(node.right);
        const a = lc + rc + 1;
        const b = Math.min(a, la + rb, ra + lb);
        const c = Math.min(a, lb + rb);
        return [a, b, c];
    };
    return dfs(root)[1];
}

二叉树专题的其他题目

查看二叉树全部题目 →