【题目描述】
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "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 forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.
Determine the maximum amount of money the thief can rob tonight without alerting the police.
在上次打劫完一条街道之后和一圈房屋之后，窃贼又发现了一个新的可以打劫的地方，但这次所有的房子组成的区域比较奇怪，聪明的窃贼考察地形之后，发现这次的地形是一颗二叉树。与前两次偷窃相似的是每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。
算一算，如果今晚去打劫，你最多可以得到多少钱，当然在不触动报警装置的情况下。
【题目链接】
www.lintcode.com/en/problem/house-robber-iii/
【题目解析】
此题可以使用递归。
每个节点都有两个选择，即选当前这个节点或者不选当前这个节点。如果选当前节点则不能选左右子节点，如果不选当前节点，则可以选左右子节点。所以对于每个节点，先递归求解其左右节点的值，若不选当前节点，则其最大值为max(选左节点，不选左节点)+max(选右节点，不选右节点)；若选当前节点，则其最大值为不选左节点＋不选右节点＋当前节点值。最后再在这两个里面取较大的那个即可。
【参考答案】
网友评论