1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public static int rob(TreeNode root){
		f(root);
		return Math.max(yes,no);
	}

	// 全局变量,完成了X子树的遍历,返回之后
	// yes变成,X子树在偷头节点的情况下,最大的收益
	public static int yes;

	// 全局变量,完成了X子树的遍历,返回之后
	// no变成,X子树在不偷头节点的情况下,最大的收益
	public static int no;
	public static void f(TreeNode root){
		if(root==null){
			yes = 0;
			no =0;// 边界条件
		}else{
			int y = root.val;  // 偷当前节点的收益,先加上节点值
			int n = 0;         // 不偷当前节点的收益

			f(root.left);      // 递归处理左子树
			y += no;           // 如果偷当前节点,只能累加左子树"不偷根"的收益
			n += Math.max(yes, no);  // 如果不偷当前节点,左子树可以自由选择

			f(root.right);     // 递归处理右子树
			y += no;           // 同样,偷当前节点只能累加右子树"不偷根"的收益
			n += Math.max(yes, no);  // 不偷当前节点,右子树自由选择
			yes = y;
			no = n;//更新全局状态
		}
	}