题目链接
    image.png

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode() {}
    8.  *     TreeNode(int val) { this.val = val; }
    9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
    10.  *         this.val = val;
    11.  *         this.left = left;
    12.  *         this.right = right;
    13.  *     }
    14.  * }
    15.  */
    16. class Solution {
    17.     public int rob(TreeNode root) {
    18.         int[] a = dfs(root);
    19.         return Math.max(a[0], a[1]);
    20.     }
    22.     public int[] dfs(TreeNode root) {
    23.         if(root == null) {
    24.             return new int[]{0, 0};
    25.         }
    27.         int[] l = dfs(root.left);
    28.         int[] r = dfs(root.right);
    30.         // 选择的值
    31.         int select = l[1] + r[1] + root.val;
    32.         // 不选择的值
    33.         int noselect = Math.max(l[0],l[1]) + Math.max(r[0], r[1]); 
    35.         return new int[]{select, noselect};
    36.     }
    37. }