Question

Formatted question description: https://leetcode.ca/all/337.html

 337	House Robber III

 The thief has found himself a new place for his thievery again.
 There is only one entrance to this area, called the "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 forms a binary tree".
 It will automatically contact the police if two directly-linked houses were broken into on the same night.

 Determine the maximum amount of money the thief can rob tonight without alerting the police.

 Example 1:

 Input: [3,2,3,null,3,null,1]

    3
   / \
  2   3
  \    \
   3    1

 Output: 7
 Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

 Example 2:

 Input: [3,4,5,1,3,null,1]

    3
   / \
  4   5
 / \   \
1   3   1

 Output: 9
 Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

 @tag-tree

Algorithm

`Note` on a common-sense mistake on this question

The example given above seems to be stolen every other node, but in fact it is not necessarily only every other, such as the following example

If you steal one by every other node, then 4+2=6 or 1+3=4. In fact, the optimal solution should be 4+3=7, which is two times apart, so it is purely how to get it. Then this kind of problem is a typical recursive problem. Can be done using backtracking.

Code

public class House_Robber_III {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */


    class Solution_singleRecursion {

        public int rob(TreeNode root) {

            return Math.max(dfs(root, true), dfs(root, false));
        }

        private int dfs(TreeNode root, boolean isCurrentRootRobbed) {

            if (root == null) {
                return 0;
            }

            if (isCurrentRootRobbed) {
                return root.val + dfs(root.left, false) + dfs(root.right, false);
            } else {
                // child can be either rob or no-rob
                return Math.max(dfs(root.left, true), dfs(root.left, false)) + Math.max(dfs(root.right, true), dfs(root.right, false));
            }
        }
    }

    class Solution {
        /*
            1. node value can be negative?

         */
        public int rob(TreeNode root) {
            if (root == null) {
                return 0;
            }

            return Math.max(target(root), skip(root));
        }

        private int target(TreeNode root) {
            if (root == null) {
                return 0;
            }

            return root.val + skip(root.left) + skip(root.right);
        }

        private int skip(TreeNode root) {
            if (root == null) {
                return 0;
            }

            // @note: not target, but rob again => 因为理论上可以连续skip两层
//            return target(root.left) + target(root.right);
            return rob(root.left) + rob(root.right);
        }
    }
}

############

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Map<TreeNode, Integer> memo;

    public int rob(TreeNode root) {
        memo = new HashMap<>();
        return dfs(root);
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (memo.containsKey(root)) {
            return memo.get(root);
        }
        int a = dfs(root.left) + dfs(root.right);
        int b = root.val;
        if (root.left != null) {
            b += dfs(root.left.left) + dfs(root.left.right);
        }
        if (root.right != null) {
            b += dfs(root.right.left) + dfs(root.right.right);
        }
        int res = Math.max(a, b);
        memo.put(root, res);
        return res;
    }
}

// OJ: https://leetcode.com/problems/house-robber-iii/
// Time: O(N)
// Space: O(H)
class Solution {
    pair<int, int> dfs(TreeNode* root) { // rob, skip
        if (!root) return { 0, 0 }; 
        auto [lr, ls] = dfs(root->left);
        auto [rr, rs] = dfs(root->right);
        return { root->val + ls + rs, max(lr, ls) + max(rr, rs) };
    }
public:
    int rob(TreeNode* root) {
        auto [r, s] = dfs(root);
        return max(r, s);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rob(self, root: TreeNode) -> int:
        return max(self.dfs(root, True), self.dfs(root, False))

    # if no cache, then running time over limit
    @cache 
    def dfs(self, root: TreeNode, isCurrentRootRobbed: bool) -> int:
        if not root:
            return 0
        
        if isCurrentRootRobbed:
            return root.val + self.dfs(root.left, False) + self.dfs(root.right, False)
        else:
            return max(self.dfs(root.left, True), self.dfs(root.left, False)) + max(self.dfs(root.right, True), self.dfs(root.right, False))

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def rob(self, root):
    """
    :type root: TreeNode
    :rtype: int
    """

    def dfs(root):
      if not root:
        return 0, 0
      lpre, lppre = dfs(root.left)
      rpre, rppre = dfs(root.right)
      return max(root.val + lppre + rppre, lpre + rpre), lpre + rpre

    return dfs(root)[0]

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
	memo := make(map[*TreeNode]int)
	var dfs func(root *TreeNode) int
	dfs = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		if _, ok := memo[root]; ok {
			return memo[root]
		}
		a := dfs(root.Left) + dfs(root.Right)
		b := root.Val
		if root.Left != nil {
			b += dfs(root.Left.Left) + dfs(root.Left.Right)
		}
		if root.Right != nil {
			b += dfs(root.Right.Left) + dfs(root.Right.Right)
		}
		res := max(a, b)
		memo[root] = res
		return res
	}
	return dfs(root)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

337 - House Robber III

Question

Algorithm

`Note` on a common-sense mistake on this question

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note on a common-sense mistake on this question

Code

All Problems

All Solutions

`Note` on a common-sense mistake on this question