[leetCode]968. 监控二叉树

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { // 每个节点右三种状态：0.无覆盖 1.有摄像头 2.有覆盖 private final Integer UNCOVERED = 0, COVERED = 2, HASCAM = 1; private Integer result = 0; public int minCameraCover(TreeNode root) { // 4. 递归结束如果根节点无覆盖则需要放摄像头 if (UNCOVERED == traversal(root)) { result++; } return result; } private int traversal(TreeNode cur) { // 空节点，该节点有覆盖 if (cur == null) return COVERED; int left = traversal(cur.left); // 左 int right = traversal(cur.right); // 右 // 逻辑处理 中 // 1.如果左子节点和右子节点都覆盖了那么当前节点为无覆盖 if (left == COVERED && right == COVERED) return 0; // 2.有一个孩子没覆盖，父节点就应该放摄像头 if (left == 0 || right == 0) { result++; return HASCAM; } // 3.如果左右节点只要其中一个有摄像头则该节点为覆盖状态 if (left == 1 || right == 1) { return COVERED; } return -1; } }

简化版本:

class Solution { int res = 0; public int minCameraCover(TreeNode root) { if (traversal(root) == 0) { res++; } return res; } // 无覆盖: 0, 放置摄像头: 1, 覆盖: 2 private int traversal(TreeNode node) { if (node == null) return 2; int left = traversal(node.left); int right = traversal(node.right); if (left == 2 && right == 2) { return 0; } else if (left == 0 || right == 0) { res++; return 1; } else { return 2; } } }