Leetcode 337 打家劫舍 III
题意理解：
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为
root。除了
root之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。给定二叉树的
root。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
这里的打家劫舍不同之处在于：状态转移是在一颗树上
限制要求是：相邻不能偷
所以：
偷了根节点，左右孩子节点不能偷
偷了左右孩子，根节点不能偷
解题思路：
这里使用回溯法来遍历每个节点
每个节点都有两种状态：偷当前节点，和不偷当前节点
所以我们在每层设置一个dp数组： dp[0]表示不偷所能获得的最大金额， dp[1]表示偷所能获得的最大金额。
所以每层返回一个dp数组。
dp[0]=max(偷左，不偷左）+ max(偷右，不偷右)
dp[1]=不偷左+不偷右+根
最后的结果是：
max(dp[0],dp[1])
1.解题
public int rob(TreeNode root) {int[] dp=new int[2];dp=travel(root);return Math.max(dp[0],dp[1]);}public int[] travel(TreeNode root){int[] dp=new int[2];if(root==null) return dp;int[] left_dp=travel(root.left);int[] right_dp=travel(root.right);dp[0]=Math.max(left_dp[0],left_dp[1])+Math.max(right_dp[0],right_dp[1]);dp[1]=left_dp[0]+right_dp[0]+root.val;return dp;}2.分析
时间复杂度：O(n)
空间复杂度：O(n)