337. House Robber III

Leetcode

https://leetcode.com/problems/house-robber-iii/

題目

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.

Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.

Example 1:

Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

解答

• 方法一

Recursion

var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        
        if (!node.left && !node.right) {
            return [node.val, 0]
        }
        
        const leftDFS = dfs(node.left);
        const rightDFS = dfs(node.right);
        
        const notIncludeChildCase = leftDFS[1] + rightDFS[1];
        const firstCase = leftDFS[0] + rightDFS[0];
        const secondCase = leftDFS[0] + rightDFS[1];
        const thirdCase = leftDFS[1] + rightDFS[0];
        
        // 第一個元素代表加入自己最大值，第二個元素代表不加入自己最大值
        return [
          notIncludeChildCase + node.val,
          Math.max(notIncludeChildCase, firstCase, secondCase, thirdCase)
        ];
    }
    
    const result = dfs(root);
    return Math.max(...result);
};

Runtime: 100 ms, faster than 54.72% of JavaScript online submissions for House Robber III.

Memory Usage: 47.5 MB, less than 20.47% of JavaScript online submissions for House Robber III.

• 方法二

類似方法一的 recursion (稍微簡化)

var rob = function(root) {
    const dfs = (node) => {
        if (!node) return [0, 0];
        
        const leftDFS = dfs(node.left);
        const rightDFS = dfs(node.right);
        
        const notIncludeNodesCase = node.val + leftDFS[1] + rightDFS[1];
        // 左右子節點取最大值的那一個再加起來
        const includeNodesCase = Math.max(...leftDFS) + Math.max(...rightDFS);
        
        return [notIncludeNodesCase, includeNodesCase];
    }
    
    const result = dfs(root);
    return Math.max(...result);
};

Runtime: 109 ms, faster than 41.15% of JavaScript online submissions for House Robber III.

Memory Usage: 47.8 MB, less than 14.62% of JavaScript online submissions for House Robber III.

• 方法三

利用 hashmap 紀錄拜訪過節點的最大值

var rob = function(root) {
    const robResult = new Map();
    const notRobResult = new Map();
    
    const helper = (node, isParentRobbed) => {
        if(!node) return 0;
        
        if (isParentRobbed) {
            if(robResult.has(node)) {
                return robResult.get(node);
            }
            const result = helper(node.left, false) + helper(node.right, false); 
            robResult.set(node, result);
            return result;
        } else {
            if(notRobResult.has(node)) {
                return notRobResult.get(node);
            }
            // 選擇此節點
            const rob = node.val + helper(node.left, true) + helper(node.right, true); 
            // 不選擇此節點
            const notRob = helper(node.left, false) + helper(node.right, false); 
            const result = Math.max(rob, notRob);
            // Don't quite sure why this can work?
            notRobResult.set(node, result);
            return result;
        }
    }
    
    return helper(root, false);
};

Runtime: 139 ms, faster than 13.08% of JavaScript online submissions for House Robber III.

Memory Usage: 48.6 MB, less than 8.46% of JavaScript online submissions for House Robber III.