题解 | #打家劫舍(三)#
打家劫舍(三)
https://www.nowcoder.com/practice/58dad1054a0b41ab9b076e5bcc3160dc
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的解法。
建树过程：
- 先规定treeNodes第一个结点必须是root结点 =》node.parent === 0
- 然后从treeNodes的第二个开始遍历所有节点，根据parent，找到cur当前节点的父节点所在的位置treeNodes[parent - 1]
- 结点放左边还是右边无所谓，对题不影响，就统一先放左，左有了再放右
建完树之后，才是这道题打家劫舍的dp做法：
- 定义一个长度为2的数组，[不抢，抢]
- 采用后序遍历的方式遍历树，这样才能做到从底部往上遍历；
- 对于中间结点 状态 的 选择 有两种，不抢当前节点 和 抢当前节点
- 不抢当前节点，就必须抢child节点，notRob = LeftMax + RightMax => notRob = max(...left) + max(...right)
- 抢当前节点, 子结点就不能抢了：doRob = curVal + LeftNotRob + RightNotRob => doRob = node.val + left[0] + right[0];
- 返回当前节点的状态时的状态，nodeMax = return [ notRob， doRob ]
