Massive Algorithms: LeetCode 968 - Binary Tree Cameras

LeetCode 968 - Binary Tree Cameras

https://leetcode.com/problems/binary-tree-cameras/

Given a binary tree, we install cameras on the nodes of the tree.

Each camera at a node can monitor its parent, itself, and its immediate children.

Calculate the minimum number of cameras needed to monitor all nodes of the tree.

Example 1:

Input: [0,0,null,0,0]
Output: 1
Explanation: One camera is enough to monitor all nodes if placed as shown.

Example 2:

Input: [0,0,null,0,null,0,null,null,0]
Output: 2
Explanation: At least two cameras are needed to monitor all nodes of the tree. The above image shows one of the valid configurations of camera placement.

Note:

The number of nodes in the given tree will be in the range [1, 1000].
Every node has value 0

X. DP
http://reeestart.me/2019/01/02/LeetCode-968-Binary-Tree-Camera/

https://www.acwing.com/solution/LeetCode/content/698/
f(i,0)f(i,0) 表示 ii 结点被父结点监控的所需要的最少摄像头数量；同理，f(i,1)f(i,1) 和 f(i,2)f(i,2) 分别表示被自己监控和被某个儿子结点监控所需要的最少摄像头数量。
我们通过递归的方式来更新 ff 数组；对于叶结点，f(i,0)=0f(i,0)=0，f(i,1)=1f(i,1)=1，f(i,2)=+∞f(i,2)=+∞。
对非叶结点转移时，f(i,0)f(i,0) 不能取儿子结点中被父结点监控，所以很容易写出 f(i,0)=min(f(j1,1)+f(j2,2))+min(f(j2,1)+f(j2,2))f(i,0)=min(f(j1,1)+f(j2,2))+min(f(j2,1)+f(j2,2))；f(i,1)f(i,1) 可以取儿子结点中三种状态的最小值之和；f(i,2)f(i,2) 则需要某个儿子必须取“被自己监控”，其余取“被自己监控”和“被某个儿子监控”中的最小值。转移方程都可以很容易的写出。
最终答案为，min(f(root,1),f(root,2))min(f(root,1),f(root,2))。
我们需要用一个哈希表，将指针映射到数字编号。

每个结点仅遍历一次，遍历某个结点仅需要常数的时间更新，故总时间复杂度为 O(n)

https://blog.csdn.net/zjucor/article/details/85380470
考虑为了计算root节点的值，需要每个子节点收集什么信息，满足什么条件，可以有哪些状态。

首先，子节点的子节点必须是合理，而子节点可以是被cover到的，也可以没有cover到（当前root节点可以cover子节点）。所以子节点有2个因素会影响父节点的计算：

1. 当前子节点有没有被cover（没有被cover的话，父节点就一定要cover当前子节点）

2. 当前子节点有没有放camera（放了的话父节点就被cover了）

所以，为了计算父节点的值，需要收集子节点3（有1种状态不可能出现）种状态的值：

1. 子节点没被cover（子节点一定没有camera）

2. 子节点被cover，而且子节点处没放camera

3. 子节点被cover，而且子节点处放了camera

Let's try to cover every node, starting from the top of the tree and working down. Every node considered must be covered by a camera at that node or some neighbor.

Because cameras only care about local state, we can hope to leverage this fact for an efficient solution. Specifically, when deciding to place a camera at a node, we might have placed cameras to cover some subset of this node, its left child, and its right child already.

Algorithm

Let solve(node) be some information about how many cameras it takes to cover the subtree at this node in various states. There are essentially 3 states:

[State 0] Strict subtree: All the nodes below this node are covered, but not this node.
[State 1] Normal subtree: All the nodes below and including this node are covered, but there is no camera here.
[State 2] Placed camera: All the nodes below and including this node are covered, and there is a camera here (which may cover nodes above this node).

Once we frame the problem in this way, the answer falls out:

To cover a strict subtree, the children of this node must be in state 1.
To cover a normal subtree without placing a camera here, the children of this node must be in states 1 or 2, and at least one of those children must be in state 2.
To cover the subtree when placing a camera here, the children can be in any state.

public int minCameraCover(TreeNode root) {

int[] ans = solve(root);

return Math.min(ans[1], ans[2]);

}

// 0: Strict ST; All nodes below this are covered, but not this one

// 1: Normal ST; All nodes below and incl this are covered - no camera

// 2: Placed camera; All nodes below this are covered, plus camera here

public int[] solve(TreeNode node) {

if (node == null)

return new int[] { 0, 0, 99999 };

int[] L = solve(node.left);

int[] R = solve(node.right);

int mL12 = Math.min(L[1], L[2]);

int mR12 = Math.min(R[1], R[2]);

int d0 = L[1] + R[1];

int d1 = Math.min(L[2] + mR12, R[2] + mL12);

int d2 = 1 + Math.min(L[0], mL12) + Math.min(R[0], mR12);

return new int[] { d0, d1, d2 };

}

https://blog.csdn.net/likewind1993/article/details/85537408
int minCameraCover(TreeNode* root)
{
vector<int> ans = solve(root);
//由于状态0不满足覆盖条件，因此当当前节点为root时，选择满足状态1和状态2中的最小值
return min(ans[1], ans[2]);

}
vector<int> solve(TreeNode* node) {
//按照之前递归出口的分析，这里将MAX_VALUE设为了99999
if(node == NULL)
return vector<int>{0, 0, 99999};

//对当前节点的左子节点以及右子节点计算最优解值
vector<int> L = solve(node->left);
vector<int> R = solve(node->right);
//求解左子节点以及右子节点中满足的状态1、状态2的最小值
//也就是全部覆盖左子树、右子树所需相机数的最优解
int mL12 = min(L[1], L[2]);
int mR12 = min(R[1], R[2]);
//当当前节点为状态0时，按照【总结1】，两个子节点必须处于状态1.
//因此得到的最优解为L[1]+R[1]
int d0 = L[1] + R[1];
//当当前节点为状态1时，按照【总结2】，两个子节点中至少有一个节点处于状态2，另一个子节点处于状态1或2
//因此得到的最优解为这两种情况的最小值
int d1 = min(L[2] + mR12, R[2] + mL12);
//当当前节点为状态2时，按照【总结3】, 只要求得两个子节点的最优解在加上当前节点放置的相机数1即可
int d2 = 1 + min(L[0], mL12) + min(R[0], mR12);

return vector<int>{d0, d1, d2};
}

X. Greedy
https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS

Consider a node in the tree.
It can be covered by its parent, itself, its two children.
Four options.

Consider the root of the tree.
It can be covered by left child, or right child, or itself.
Three options.

Consider one leaf of the tree.
It can be covered by its parent or by itself.
Two options.

If we set a camera at the leaf, the camera can cover the leaf and its parent.
If we set a camera at its parent, the camera can cover the leaf, its parent and its sibling.

We can see that the second plan is always better than the first.
Now we have only one option, set up camera to all leaves' parent.

Here is our greedy solution:

Set cameras on all leaves' parents, thenremove all covered nodes.
Repeat step 1 until all nodes are covered.

Explanation:

Apply a recusion function dfs.
Return 0 if it's a leaf.
Return 1 if it's a parent of a leaf, with a camera on this node.
Return 2 if it's coverd, without a camera on this node.

For each node,
if it has a child, which is leaf (node 0), then it needs camera.
if it has a child, which is the parent of a leaf (node 1), then it's covered.

If it needs camera, then res++ and we return 1.
If it's covered, we return 2.
Otherwise, we return 0.

    int res = 0;
    public int minCameraCover(TreeNode root) {
        return (dfs(root) < 1 ? 1 : 0) + res;
    }

    public int dfs(TreeNode root) {
        if (root == null) return 2;
        int left = dfs(root.left), right = dfs(root.right);
        if (left == 0 || right == 0) {
            res++;
            return 1;
        }
        return left == 1 || right == 1 ? 2 : 0;
    }

因为仔细想一下, 对于叶子结点Leaf来说, 是根本不可能放camera的. 肯定是放在parent of leaf划算.

因此最直接的方法就是把tree转换成一个graph, 然后循环一下步骤直到没有结点位置:

remove all leaf nodes.
res += (number of current leaf nodes)
remove all leaf nodes. (parent of actual leaf)
remove all leaf nodes. (parent of the node with camera)
Go back to step 1.

这个方法代码写起来估计有点烦, 大神们连graph都不用建, 直接用遍历一遍tree就搞定. 自己欣赏吧.


private static final int LEAF = 0;

private static final int HAS_CAMERA = 1;

private static final int NO_NEED_CAMERA = 2;



int res = 0;

public int minCameraCover(TreeNode root) {

if (root == null) return 0;



if (dfs(root) == LEAF) res++;



return res;

}



private int dfs(TreeNode root) {

if (root == null) return NO_NEED_CAMERA;

if (root.left == null && root.right == null) return LEAF;



int l = dfs(root.left);

int r = dfs(root.right);



if (l == LEAF || r == LEAF) {

res++;

return HAS_CAMERA;

} else if (l == HAS_CAMERA || r == HAS_CAMERA) {

return NO_NEED_CAMERA;

} else {

return LEAF;

}

}

https://raw.githubusercontent.com/cherryljr/LeetCode/master/Binary%20Tree%20Cameras.java

 * Approach: Divide and Conquer with Greedy
 * 基本上所有 树 类型的题目，都是差不多这个套路。
 * 不过本题难点在于能不能想出这个贪心的处理。
 * （其实也不难，因为在推理状态的时候，其实挺自然地就能想出来了）
 * 本道题目其实算是 Distribute Coins in Binary Tree 的一个升级变形题。
 *
 * 首先我们定义一个 Func 作用为：在当前node的子树中放置照相机，并保证每个节点都能被监控到。
 * 同时，定义一个全局变量 res，每次放置相机的时候，加上需要的个数即可。
 * 然后，我们就会遇到本题的难点：
 *  放置相机之后，其能够监听 当前节点 + 左右孩子 + 节点的父亲。
 * 因此我们需要知道在 Func 处理之后，每个节点的状态是什么。（照相机到底放在哪个点上）
 * 而放置方法就用到了贪心的策略：
 *  因为放在 叶子节点的父亲节点 上能监控到的点比放在 叶子节点 上要多，
 *  故我们在放置相机的时候，会选择放在 left.parent 上。
 *  然后将已经被监控的节点去除掉，再考虑未被监控的点。
 *  这其实也就是 递归调用 的一个过程。
 * 因此这里定义：
 *  return 0：代表当前节点是 叶子 节点
 *  return 1：代表当前节点是 放置相机 的节点（即叶子节点的父亲）
 *  return 2：代表当前节点是 已经被监控 的节点（可以理解为放置了相机的节点的父亲）
 * 然后，只有当 left == 0 || right == 0.即当前节点为 leaf.parent 时，我们需要放置相机，此时 res++
 * 最后，值得注意的一点是：
 *  当我们对 root 处理之后，我们需要查询 root 是否已经被监控到。
 *  如果没有的话，我们需要多放置一台相机来监控 root.
 *  eg. 整颗树只有一个节点，此时我们对 root 处理完后发现，dfs(root) 返回值为 0
 *  代表去除被监控的点后，root作为leaf还未被监控，此时我们需要对结果加一。
 *

    public int minCameraCover(TreeNode root) {
        int state = dfs(root);
        return res + (state == 0 ? 1 : 0);
    }

    // Return 0 if it's a leaf.
    // Return 1 if it's a parent of a leaf, with a camera on this node
    // Return 2 if it's coverd, without a camera on this node
    // (like the parent node of a node with camera)
    private int dfs(TreeNode root) {
        if (root == null) {
            return 2;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        if (left == 0 || right == 0) {
            res++;
            return 1;
        }
        return left == 1 || right == 1 ? 2 : 0;
    }

https://leetcode.com/articles/binary-tree-cameras/

Instead of trying to cover every node from the top down, let's try to cover it from the bottom up - considering placing a camera with the deepest nodes first, and working our way up the tree.

If a node has its children covered and has a parent, then it is strictly better to place the camera at this node's parent.

If a node has children that are not covered by a camera, then we must place a camera here. Additionally, if a node has no parent and it is not covered, we must place a camera here.

int ans;

Set<TreeNode> covered;

public int minCameraCover(TreeNode root) {

ans = 0;

covered = new HashSet();

covered.add(null);

dfs(root, null);

return ans;

}

public void dfs(TreeNode node, TreeNode par) {

if (node != null) {

dfs(node.left, node);

dfs(node.right, node);

if (par == null && !covered.contains(node) || !covered.contains(node.left) || !covered.contains(node.right)) {

ans++;

covered.add(node);

covered.add(par);

covered.add(node.left);

covered.add(node.right);

}

http://www.noteanddata.com/leetcode-968-Binary-Tree-Cameras-java-solution-note.html

首先对于任意一个节点，只有四种可能是会让这个节点被cover的，一种是父节点有camera，一种是自己有camera，一种是左节点有camera，一种是右节点有camera
那么如果我们用dfs写，首先需要传入的状态有父节点是否有camera，因为这个会影响到当前节点是否一定要放置camera的问题
然后，对于每个节点，我们可以选择当前是否放置camera，这里遇到一个比较tricky的问题是，如果父节点没有camera, 当前节点也选择不放置camera的话，
那么，在左节点或者右节点必须要放置一个camera, 才可以保证当前节点被cover，所以，这里会需要传入另外一个状态force, 用来表示某个节点是否一定要放置camera（就是上一次访问的节点的子节点），
到这里，我们可以定义递归函数如下
int dfsmin(TreeNode node, boolean parentVisited, boolean force)
函数的实现，就是对几种情况分别做处理，然后取合法的最小值就好
当然，这样做会超时，原因是递归的过程中，对很多节点做了大量的重复计算，所以我们可能会考虑用一个Map<TreeNode, Integer>来做记忆化搜索，可是实际上这样提交以后会几乎全错，原因是这里会对每个node做多次计算，但是每次状态都是不一样的，比如parentvisited的值会不一样，所以这里需要定义一个state，来对这个递归过程做记忆

public int minCameraCover(TreeNode root) {
    return dfsmin(root, false, false, new HashMap<>());
}

// each dfsmin will care about how to cover the current node
int dfsmin(TreeNode node, boolean parentVisited, boolean force, Map<State, Integer> map) {
    if(null == node) return 0;
    
    State state = new State(node, parentVisited, force);
    // note we have to use the state as the key, use the node as the key will give wa
    // because each node is called multiple times with different state
    if(map.containsKey(state)) {  
        return map.get(state);
    }
    
    if(parentVisited) {
        // case 1: visit current node
        int min1 = 1 + dfsmin(node.left, true, false, map) + dfsmin(node.right, true, false, map);
        // case 2 : not visit current node (because current node is covered by parent)
        int min2 = dfsmin(node.left, false, false, map) + dfsmin(node.right, false, false, map);
        int min = Math.min(min1, min2);
        map.put(state, min);

        return min;
    }
    else {
        // case 1: visit current node
        int min = 1 + dfsmin(node.left, true, false, map) + dfsmin(node.right, true, false, map);
        
        if(!force) {
            // case 2: not visit cur, visit left (if left exist) so that left can cover cur
            if(node.left != null) {
                int min2 = dfsmin(node.left, false, true, map) + dfsmin(node.right, false, false, map);    
                min = Math.min(min, min2);
            }
            if(node.right != null) {
                int min3 = dfsmin(node.left, false, false, map) + dfsmin(node.right, false, true, map);
                min = Math.min(min, min3);
            }
        }
        
        map.put(state, min);
        
        return min;
    }
}

static class State {
    private TreeNode node;
    private boolean parentVisited;
    private boolean force;
    public State(TreeNode node, boolean parentVisited, boolean force) {
        this.node = node;
        this.parentVisited = parentVisited;
        this.force = force;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        State state = (State) o;
        return parentVisited == state.parentVisited &&
                force == state.force &&
                Objects.equals(node, state.node);
    }

    @Override
    public int hashCode() {
        return Objects.hash(node, parentVisited, force);
    }
}

时间复杂度

O(N*4), 对于每个node，有4种不同的状态，分别做了搜索

空间复杂度

O(N*4), 对于每个状态都做了搜索

LeetCode 968 - Binary Tree Cameras

Explanation:

时间复杂度

空间复杂度

Labels

Popular Posts