Problem:
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.
Never expected such a simple solution to this problem. Once there is a clarity on the problem, solution may be simple. I learnt this solution from https://leetcode.com/problems/binary-tree-cameras/discuss/1778400/C%2B%2B-Greedy-DFS-Super-Clean-Solution.-Explained-via-a-Story. He is awesome, so creative.
3 simple conditions:
— If node not exists, no camera needed
— If any one children needs a camera, place a camera on parent and increment number of cameras
— If any one children has a camera, parent does not need a camera
— By default (if above conditions not met), return camera needed
Return the values according to the above conditions
int getnumc(struct TreeNode* nd, int *nc){
/* as node is null no camera needed */
if (!nd)
return NO_CAMERA_NEEDED;
/* by default , each node needs a camera */
int lret,rret;
lret = getnumc(nd->left, nc);
rret = getnumc(nd->right, nc);
/* if any child need a camera, increment number of cameras.
place a camera
*/
if (lret == CAMERA_NEEDED || rret == CAMERA_NEEDED){
(*nc)++;
return HAS_CAMERA;
}
/* if any child a camera,
parent does not need a camera */
if ((lret == HAS_CAMERA) || (rret == HAS_CAMERA))
return NO_CAMERA_NEEDED;
return CAMERA_NEEDED;
}int minCameraCover(struct TreeNode* root){
int ret, nc=0;
ret = getnumc(root, &nc);
if (ret == CAMERA_NEEDED) nc++;
return(nc);
}
One wrong approach:
I tried the below solution. Thought if left child is returning camera needed, parent has to compulsorily place a camera, So in this case why to go over the right child , just place a camera and return.
But missed this point : this right child may not be a single node, it can be a sub tree.
So we should be careful in optimizing the solutions :) .
#ifdef NON_WORK
/* if left child is returning camera needed,
camera will be placed at parent,
in this case, calling this func for right child is not rqd
But in this right child may be a subtree, this solution ignores going through the right subtree which is incorrect*/
int getnumc(struct TreeNode* nd, int *nc){
/* as node is null no camera needed */
if (!nd)
return NO_CAMERA_NEEDED;
/* two choices */
/* place camera on node or on children */
int lret;
lret = getnumc(nd->left, nc);
if (lret == CAMERA_NEEDED){
(*nc)++;
return HAS_CAMERA;
}
int rret = getnumc(nd->right, nc);
/* if any child need a camera, increment number of cameras.
place a camera
*/
if (rret == CAMERA_NEEDED){
(*nc)++;
return HAS_CAMERA;
}
/* if any child a camera,
parent does not need a camera */
if ((lret == HAS_CAMERA) || (rret == HAS_CAMERA))
return NO_CAMERA_NEEDED;
return CAMERA_NEEDED;
}
#endif