337.打家劫舍-iii ​

const map = new Map();
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  if (!root) return 0;
  if (!root.left && !root.right) return root.val;
  if (map.has(root)) {
    return map.get(root);
  }
  // 偷父节点
  let val1 = root.val;
  if (root.left) val1 += rob(root.left.left) + rob(root.left.right);
  if (root.right) val1 += rob(root.right.left) + rob(root.right.right);

  let val2 = rob(root.left) + rob(root.right);
  const res = Math.max(val1, val2);
  map.set(root, res);
  return res;
};

const map = new Map();
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  if (!root) return 0;
  if (!root.left && !root.right) return root.val;
  if (map.has(root)) {
    return map.get(root);
  }
  // 偷父节点
  let val1 = root.val;
  if (root.left) val1 += rob(root.left.left) + rob(root.left.right);
  if (root.right) val1 += rob(root.right.left) + rob(root.right.right);

  let val2 = rob(root.left) + rob(root.right);
  const res = Math.max(val1, val2);
  map.set(root, res);
  return res;
};

function robTree(cur) {
  if (!cur) return [0, 0]; // 长度为2的数组，0：不偷，1：偷
  const left = robTree(cur.left);
  const right = robTree(cur.right);
  // 偷父节点，左右节点不偷
  const val1 = cur.val + left[0] + right[0];
  // 不偷父节点, 左边节点偷或者不偷的最大值 + 右边节点偷或者不偷的最大值
  const val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
  return [val2, val1];
}
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  return Math.max(...robTree(root));
};

function robTree(cur) {
  if (!cur) return [0, 0]; // 长度为2的数组，0：不偷，1：偷
  const left = robTree(cur.left);
  const right = robTree(cur.right);
  // 偷父节点，左右节点不偷
  const val1 = cur.val + left[0] + right[0];
  // 不偷父节点, 左边节点偷或者不偷的最大值 + 右边节点偷或者不偷的最大值
  const val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
  return [val2, val1];
}
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function (root) {
  return Math.max(...robTree(root));
};