LeetCode 968. 监控二叉树

Categories:

题目描述
思路分析
1. 解法一：树形 DP（推荐）
相似题目

题目描述

✅ 968. 监控二叉树

思路分析

解法一：树形 DP（推荐）

核心思路：

对每个节点定义三种状态：有相机、已覆盖、待覆盖。

后序遍历，先判断左右子树状态，再决定当前节点是否放置相机。

若任一子节点待覆盖，则当前必须放相机；若任一子节点有相机，则当前已覆盖；否则当前待覆盖。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树的高度（递归栈）。

class Solution {
    private int cameras = 0;

    public int minCameraCover(TreeNode root) {
        if (dfs(root) == 2) {
            cameras++;
        }
        return cameras;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 1;
        }

        int left = dfs(node.left);
        int right = dfs(node.right);

        // 子节点有待覆盖的情况，当前必须放相机
        if (left == 2 || right == 2) {
            cameras++;
            return 0;
        }

        // 子节点有相机，当前已覆盖
        if (left == 0 || right == 0) {
            return 1;
        }

        // 两侧都已覆盖，当前待覆盖
        return 2;
    }
}

func minCameraCover(root *TreeNode) int {
	const (
		hasCamera  = 0
		covered   = 1
		needCover = 2
	)

	cameras := 0

	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return covered
		}

		left := dfs(node.Left)
		right := dfs(node.Right)

		// 子节点有待覆盖的情况，当前必须放相机
		if left == needCover || right == needCover {
			cameras++
			return hasCamera
		}

		// 子节点有相机，当前已覆盖
		if left == hasCamera || right == hasCamera {
			return covered
		}

		// 两侧都已覆盖，当前待覆盖
		return needCover
	}

	if dfs(root) == needCover {
		cameras++
	}

	return cameras
}

相似题目

题目	难度	考察点
337. 打家劫舍 III	中等	树形 DP
543. 二叉树的直径	简单	后序遍历
979. 在二叉树中分配硬币	中等	树形 DP
124. 二叉树中的最大路径和	困难	树形 DP
863. 二叉树中所有距离为 K 的结点	中等	树形搜索

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/54402868