Aug 15, 2023
Edit me

#. Problem

Go to the problem on leetcode

1. My approach (DFS)

First attempt:

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)

Second attempt:

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.

Third attempt:

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)

3. Epilogue

What I’ve learned from this exercise:

  • I need to soften my brain…