题解 | #打家劫舍(三)#

const rl = require("readline").createInterface({ input: process.stdin });

const inputs = [];

rl.on('line', (line) => {
    inputs.push(line);
}).on('close', () => {
   const res = resolve(inputs);

   console.log(res);
})

function resolve(inputs) {
    const treeRoot = buildTree(inputs);
    return rob(treeRoot);
}

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

function buildTree(inputs) {
  const val = inputs[1].split(" ").map((i) => parseInt(i));
  const parent = inputs[2].split(" ");

  const treeNodes = [];
  const N = val.length;

  for (let i = 0; i < N; i++) {
    const node = new TreeNode(val[i]);
    node.parent = parent[i];
    if (node.parent === 0) {
      treeNodes.unshift(node);
    } else {
      treeNodes.push(node);
    }
  }
  let root = treeNodes[0];

  for (let i = 1; i < N; i++) {
    const cur = treeNodes[i];

    const parent = cur.parent;
    if (treeNodes[parent - 1].left === null) {
      treeNodes[parent - 1].left = cur;
    } else {
      treeNodes[parent - 1].right = cur;
    }
  }

  return root;
}

function rob(root) {
  const postOrder = (node) => {
    if (!node) return [0, 0];

    const left = postOrder(node.left);
    const right = postOrder(node.right);

    const notRob = Math.max(...left) + Math.max(...right);
    const doRob = node.val + left[0] + right[0];

    return [notRob, doRob];
  };

  const res = postOrder(root);

  return Math.max(...res);
}

这道题需要手动建树，然后才是打家劫舍树形dp的解法。

建树过程：

1. 先规定treeNodes第一个结点必须是root结点 =》node.parent === 0
2. 然后从treeNodes的第二个开始遍历所有节点，根据parent，找到cur当前节点的父节点所在的位置treeNodes[parent - 1]
3. 结点放左边还是右边无所谓，对题不影响，就统一先放左，左有了再放右

建完树之后，才是这道题打家劫舍的dp做法：

1. 定义一个长度为2的数组，[不抢，抢]
2. 采用后序遍历的方式遍历树，这样才能做到从底部往上遍历；
3. 对于中间结点 状态 的 选择 有两种，不抢当前节点 和 抢当前节点
1. 不抢当前节点，就必须抢child节点，notRob = LeftMax + RightMax => notRob = max(...left) + max(...right)
2. 抢当前节点, 子结点就不能抢了：doRob = curVal + LeftNotRob + RightNotRob => doRob = node.val + left[0] + right[0];
4. 返回当前节点的状态时的状态，nodeMax = return [ notRob， doRob ]