968. Binary Tree Cameras （hard）

 You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

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

 

Example 1:

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

Example 2:

Input: root = [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.

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• Node.val == 0

A：

就是每个node， 看是否用了，  如果用了。就跳到

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

* };

*/

class Solution {

public:

int minCameraCover(TreeNode* root) {

M[nullptr] = 0;

return min(noPlaceOnRoot(root), placeOnRoot(root));

}

private:

int noPlaceOnRoot(TreeNode* root){

if(!root)

return 0;

if(!root->left && ! root->right) // no child, impossible

return INT_MAX;

if(!root->left){

return placeOnRoot(root->right);

}else if(!root->right){

return placeOnRoot(root->left);

}else{ // both are not null

int useLeftChild = placeOnRoot(root->left) + minCameraCover(root->right);

int useRightChild = placeOnRoot(root->right) + minCameraCover(root->left);

return min(useLeftChild, useRightChild);

}

}

// if root is placed a camera,

int placeOnRoot(TreeNode* root){

if(!root)

return INT_MAX;

if(M.find(root) != M.end()){

return M.find(root)->second;

}

int l = 0, r = 0;

if(root->left)

l = minCameraCover(root->left->left) + minCameraCover(root->left->right);

if(root->right)

r= minCameraCover(root->right->left) + minCameraCover(root->right->right);

M[root] = 1 + l + r;

return M[root];

}

//the minimum # of cameras in binary tree if placed at root

unordered_map<TreeNode*, int> M; // insert nullptr, to avoid checking

};

NOTE：  这里，LC的test case感觉是错的

[0,null,0,null,0,null,0,null,0,0,0,null,null,0,0]

我的输出是4， 他说expect 3. 但是我画了图，感觉4 才对