algoadvance

Leetcode 337. House Robber III

Problem Statement

You are given the root of a binary tree representing houses along a street. Each node contains a non-negative integer representing the amount of money stashed in that house. The robber cannot rob two directly connected nodes (i.e., they cannot rob a parent and its direct child). Determine the maximum amount of money the robber can rob without alerting the police.

Clarifying Questions

  1. What are the node values?
    • The values are non-negative integers representing the amount of money stashed in each house.
  2. Can the tree be empty?
    • Yes, the tree can be empty. In that case, the maximum amount of money is zero.
  3. Can the tree be unbalanced?
    • Yes, the binary tree can be unbalanced.
  4. Is there a limit to the number of nodes in the tree?
    • There is no specific limit mentioned, but we can assume it to be within a reasonable range as per typical problem constraints.

Strategy

To solve this problem, we use a dynamic programming approach with depth-first search (DFS). The idea is to calculate two values for each node:

We traverse the tree bottom-up, starting from the leaf nodes, and propagate these values up to the root.

Code

Here’s the C++ code to solve this problem:

#include <iostream>
#include <unordered_map>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    std::pair<int, int> robSub(TreeNode* root) {
        if (!root) {
            return {0, 0};
        }

        auto left = robSub(root->left);
        auto right = robSub(root->right);

        // If we rob this node, we cannot rob its children
        int rob = root->val + left.second + right.second;
        // Otherwise, we take the maximum of robbing or not robbing its children
        int notRob = std::max(left.first, left.second) + std::max(right.first, right.second);

        return {rob, notRob};
    }

    int rob(TreeNode* root) {
        auto result = robSub(root);
        return std::max(result.first, result.second);
    }
};

int main() {
    // Construct the tree
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(1);

    Solution solution;
    std::cout << "Maximum amount of money that can be robbed: " << solution.rob(root) << std::endl;

    return 0;
}

Explanation

  1. TreeNode Structure: Represents a node in the binary tree.
  2. robSub Function:
    • Recursively traverses the tree.
    • Computes two values for each node:
      • rob (if we rob the current node)
      • notRob (if we do not rob the current node).
  3. rob Function:
    • Calls robSub on the root and returns the maximum of robbing or not robbing the root.

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of nodes in the tree. This is because each node is visited once, and the computation done at each node (calculating the two values) is constant time.

Space Complexity

The space complexity is (O(h)), where (h) is the height of the tree, due to the recursive call stack. In the case of a balanced tree, the height (h) is (O(\log n)), and in the case of a skewed tree, it is (O(n)).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI