一、题目
1、审题
2、分析
给出一棵二叉树，取二叉树中的节点值，其中不能获取相邻层的二叉树节点。
二、解答
1、思路
方法一、
分两种情况， 情况一： root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val
情况二： root.left.val + root.right.val
然后取这两种情况的最大值，进行递归！
public int rob(TreeNode root) {
if(root == null)
return 0;
int val = 0;
if(root.left != null)
val += rob(root.left.left) + rob(root.left.right);
if(root.right != null)
val += rob(root.right.left) + rob(root.right.right);
return Math.max(val + root.val, rob(root.left) + rob(root.right));
}
方法二、
由于方法一中，每一次递归有很多重复的计算。采用 Map <Node， val> 记录当前节点对应的最大值！减少递归的重复计算！
public int rob(TreeNode root) {
return robSub(root, new HashMap<TreeNode, Integer>());
}
private int robSub(TreeNode root, HashMap<TreeNode, Integer> map) {
if(root == null)
return 0;
if(map.containsKey(root))
return map.get(root);
int val = 0;
if(root.left != null)
val += robSub(root.left.left, map) + robSub(root.left.right, map);
if(root.right != null)
val += robSub(root.right.left, map) + robSub(root.right.right, map);
val = Math.max(val + root.val, robSub(root.left, map) + robSub(root.right, map));
map.put(root, val);
return val;
}
原文：https://www.cnblogs.com/skillking/p/11110254.html