C++ || Binary Tree Cameras || O(N) || DFS || Post-order traversal || Binary Tree

'''
class Solution {

• Start processing from [leaf nodes -> to parent nodes]
  -> As if we go from parent to child -> It's difficult to find optimal way to place camera
  Also the time complexity this way : Exponential ( O(a^n) )
  -> Go reverse (leaf -> parent) -> Fulfill needs of nodes. (automatically camera will be placed most optimal way)
  Post-order traversal (of Binary tree) -> First process childs, then parent

• Nodes will have total following 3 states :

1. Not_needed state (-1) : Camera is present in neighbourhood -> return No_camera (0) to parent
2. No_camera state (0) : Camera is not present, neither in neighbourhood -> return Has_camera (1) to parent
   // -> also place camera here first -> count++
3. Has_camera state (1) : Camera is present here -> return Not_needed (-1) to parent

Code :

int placeCamera(TreeNode* root, int& ans) {  // Time complexity : O(n)
	if(root == NULL) {
		return -1;  // Not_needed
	}
	int leftValue = placeCamera(root->left, ans);
	int rightValue = placeCamera(root->right, ans);
	if(leftValue == 0  ||  rightValue == 0) {  // Atleast 1 child has No_camera   ->  Have to place camera here
		ans++;  // 1 Camera placed (at root)  ->  children's need also fulfilled
		return 1;  // Now root Has_camera (1)
	}
	else if(leftValue == 1  ||  rightValue == 1) {  // Atleast 1 child Has_camera  ->  Camera Not_needed by root (-1)
		return -1;
	}
	else {  // Both left & right sub-tree doesn't need camera  (Not_needed (-1))
		return 0;  // Pass to root's parent  ->   root has No_camera   ->   Either root's parent will place Camera
	                                    // OR  if root is top-most node  (Camera will be placed in below function)
	}
}

public:
int minCameraCover(TreeNode* root) {
int ans = 0;
int value = placeCamera(root, ans);
if(value == 0) { // root has No_camera
ans++; // 1 Camera placed
}
return ans;
}
};
'''