title | last_updated | keywords | sidebar | comments | permalink |
---|---|---|---|---|---|
House Robber III |
Aug 15, 2023 |
algorithm |
mydoc_sidebar |
true |
house-robber-iii.html |
Comparing with ans
at the end of the node.
...
function dfs(root: number, curAmt: number, prevUsed: boolean){
if(!root) {
ans = Math.max(ans, curAmt);
return;
}
...
Problem: It will only calculate and compare one traversal(left one, or right one)
It has to return value to calculate both traversal(left + right)
...
function dfs(root: number){
if(!root.left && !root.right) {
return root.val;
}
...
Problem: This won't be able to implement the concept of skipping one for the other one.
Since it's bruteforce anyways, let's give it every possible scenario.
function rob(root: TreeNode | null): number {
function bruteForce(root: TreeNode): [number, number]{
if(!root.left && !root.right) return [root.val, 0];
const [leftUsed, leftNotUsed] = root.left? bruteForce(root.left): [0, 0];
const [rightUsed, rightNotUsed] = root.right? bruteForce(root.right) : [0, 0];
const usingMe = leftNotUsed + rightNotUsed + root.val;
const notUsingMe = Math.max(leftNotUsed + rightNotUsed, leftUsed + rightUsed, leftUsed + rightNotUsed, leftNotUsed + rightUsed);
// Same as: notUsingMe = Math.max(leftUsed, leftNotUsed) + Math.max(rightUsed, rightNotUsed);
return [usingMe, notUsingMe];
};
return Math.max(...bruteForce(root));
};
Worked.
O(N)
What I've learned from this exercise:
- I need to soften my brain...