Problem statement:
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
This House Robber-III is for binary tree data structure whereas the first 2 house robber problems are arrays (House Robber , House Robber-II).
As there is a change in data structure, the implementation changes entirely.
There are 2 types of tree traversals as tree is also a type of graph: BFS and DFS.
This problem is to not to rob parent and children together. So DFS is better approach compared to BFS.
Bottom-up approach is more suitable for this problem. As leaf nodes do not have children, robbed values of those nodes equal to their values. Do-not-rob values of those nodes will be 0.
Solution suggests to calculate two values for each node: rob-value and do-not-rob-value and consider the max value of it.
When a parent node is robbed, its children should not be robbed. When a parent node is not robbed, there is an option to either rob children nodes or not. In this case best value can be (max value of each child’s (rob value, do-not-rob value)) considered.
As solution needs a bottom up approach that is to go from leaf nodes till the root node, post order traversal is preferred.
Below is solution:
void CalcRobNotRobValues(struct TreeNode *nd, int *r, int *nr){
/* no node , both values are zero */
if (!nd){ *r = 0; *nr= 0; return;}
/* first calculate the childrens rob,not-rob values */
int lr=0, lnr=0, rr=0, rnr=0;
CalcRobNotRob(nd->left, &lr, &lnr);
CalcRobNotRob(nd->right, &rr, &rnr);
/* if robbing node, children nodes cannot be robbed
so add not-rob values of children */
*r = nd->val + lnr + rnr;
/* if not robbing node, children nodes can be robbed
so add rob values of children */
/* If not robbing this node, there is an option to rob children
or no robbing of children. Choose the max value */
if (lnr > lr) *nr = lnr;
else *nr = lr;
if (rnr > rr) *nr += rnr;
else *nr += rr;
return;
}int rob(struct TreeNode* root){
int rob=0, nr=0;
CalcRobNotRob(root, &rob, &nr);
return (rob > nr ? rob : nr);
}
Please give your comments.
