337. House Robber III

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Dynamic Programming、Tree、Depth-First Search、Binary Tree

一、題目

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.

Constraints:

  • The number of nodes in the tree is in the range [1, 10^4].
  • 0 <= Node.val <= 10^4

二、分析

  • 遵循第 i 間房若搶，則前一間房必定不能搶；第 i 間房若不搶，前一間房可搶可不搶：
    • 用一個 pair 來記錄每個節點搶與不搶的結果，最後再將兩者做比較。
      • dp[i][0] = max(dp[i-1][1], dp[i-1][0])
      • dp[i][1] = dp[i-1][0] + val[i]
    • 改寫成：
      • int pass = max(left.first, left.second) + max(right.first, right.second)
      • int rob = root->val + left.second + right.second

三、解題

1. DP

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int rob(TreeNode* root) {
    pair<int,int> res = helper(root);  // {搶, 不搶}
    return max(res.first);
}
pair<int,int> helper(TreeNode* root) {
    if (!root) return {0, 0};
    pair<int,int> left = helper(root->left);
    pair<int,int> right = helper(root-right);
    return {root->val + left.second + right.second, max(left.first, left.second) + max(right.first, right.second)};
}

回目錄 Catalog