题目

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

示例

输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

解析

小偷要是有这水平，干点什么不好。。。
首先这道题是二叉树中的动态规划，已知二叉树的递归法有递归三部曲，动态规划有动规五部曲，需要把二者结合分析一下：
1.确定递归函数的参数和返回值
参数肯定就是传进来的cur，返回值是一个数组，用来表示对于cur，偷和不偷分别得到的金钱最大值，也是是我们的dp数组，因此，对应的dp数组的含义是：
下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱。
2.确定终止条件
节点若为空，则返回，也相当于dp数组初始化了
3.确定遍历顺序
本题要使用后序遍历，因为要拿到递归函数的返回值，来进行下一步的运算
4.确定单层递归的逻辑
对于当前节点，有两种方式：偷或者是不偷
偷：则其左右孩子节点就不能偷了，即 val1 = cu.val + left[0] + right[0];
不偷：从左右孩子中偷一个最大的，即 val2 = max(left[0], left[1]) + max(right[0], right[1]);
注意：上面的0和1分别代表的是不偷和偷

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func rob(root *TreeNode) int {res := robTree(root)return max(res[0], res[1])
}func max(a, b int) int {if a > b {return a} return b
}func robTree(cur *TreeNode) []int{if cur == nil {return []int{0, 0}}// 二叉树后序遍历left := robTree(cur.Left)right := robTree(cur.Right)// 考虑去偷当前的屋子robCur := cur.Val + left[0] + right[0]// 考虑不偷当前的屋子notRobCur := max(left[0], left[1]) + max(right[0], right[1])return []int{notRobCur, robCur}
}