1、题目描述 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 2、代码详解 由于房屋是树状的,因此,我们可以使用遍历树的传统方法进行遍历(前序、中序、后续) 简单的思路是,从树低进行往上遍历,拿到最优的打劫值。可以选用后续遍历 得到每一节点的最优值,最后选取最优的结果 1.dp