题目

image.png

思路

  • 思路一：暴力递归，对于每个节点来说，如果我们选择该节点，就不能选择其子节点，如果不选择该节点就能选择其子节点，所以只要选取这几种情况的最大值即可
  • 思路二：备忘录

  • 思路三：动态规划，对于一棵树来说，选择就如暴力递归一样有两种选择，因此定义int[] res = new int[2]，res[0]表示不选取该节点能够获得的最大值，res[1]节点表示选取该节点能够获取的最大值，然后使用后续遍历节点，最后的到res结果，我们再去其最大值即可

    代码

    1.   //1.暴力递归
    2.   public int rob(TreeNode root) {
    3.       if (root == null) return 0;
    4.       return Math.max(
    5.       (root.left != null ? rob(root.left.left) + rob(root.left.right) : 0) +
    6.       (root.right != null ? rob(root.right.left) + rob(root.right.right) : 0) + root.val, 
    7.       rob(root.left) + rob(root.right));
    8.   }
    10.   //2.备忘录
    11.   Map<TreeNode, Integer> map = new HashMap<>();
    12.   public int rob(TreeNode root) {
    13.       if (root == null) return 0;
    14.       if (map.containsKey(root)) return map.get(root);
    15.       int res = Math.max(
    16.       (root.left != null ? rob(root.left.left) + rob(root.left.right) : 0) +
    17.       (root.right != null ? rob(root.right.left) + rob(root.right.right) : 0) + root.val, 
    18.       rob(root.left) + rob(root.right));
    19.       map.put(root, res);
    20.       return res;
    21.   }
    23.   //3.动态规划
    24.   public int rob(TreeNode root) {
    25.       if (root == null) return 0;
    26.       int[] res = recur(root);
    27.       return Math.max(res[0], res[1]);
    28.   }
    30.   //res[0]表示不抢劫当前节点，res[1]表示抢劫当前节点
    31.   public int[] recur(TreeNode root) {
    32.       if (root == null) return new int[2];
    33.       int[] res = new int[2];
    34.       int[] left = recur(root.left);
    35.       int[] right = recur(root.right);
    36.       res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    37.       res[1] = root.val + left[0] + right[0];
    38.       return res;
    39.   }

    打家劫舍 III