House Robber III Solutions in C++

// Source : https://leetcode.com/problems/house-robber-iii/
// Author : Calinescu Valentin, Hao Chen
// Date   : 2016-04-29


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
  /* 
 * Solution 1 - O(N log N)
 * =========
 *
 * We can use a recursive function that computes the solution for every node of the tree 
 * using the previous solutions calculated for the left and right subtrees. At every step
 * we have 2 options:
 *
 * 1) Take the value of the current node + the solution of the left and right subtrees of
 * each of the left and right children of the current node.
 * 2) Take the solution of the left and right subtrees of the current node, skipping over
 * its value.
 *
 * This way we can make sure that we do not pick 2 adjacent nodes.
 *
 * If we implemented this right away we would get TLE. Thus, we need to optimize the
 * algorithm. One key observation would be that we only need to compute the solution for
 * a certain node once. We can use memoization to calculate every value once and then
 * retrieve it when we get subsequent calls. As the header of the recursive function
 * doesn't allow additional parameters we can use a map to link every node(a pointer) to
 * its solution(an int). For every call the map lookup of an element and its insertion
 * take logarithmic time and there are a constant number of calls for each node. Thus, the
 * algorithm takes O(N log N) time to finish.
 * 
 */
class Solution {
public:
    map<TreeNode*, int> dict;
    int rob(TreeNode* root) {
        if(root == NULL)
            return 0;
        else if(dict.find(root) == dict.end())
        {
            int lwith = rob(root->left);
            int rwith = rob(root->right);
            int lwithout = 0, rwithout = 0;
            if(root->left != NULL)
                lwithout = rob(root->left->left) + rob(root->left->right);
            if(root->right != NULL)
                rwithout = rob(root->right->left) + rob(root->right->right);
            //cout << lwith << " " << rwith << " " << lwithout << " " << rwithout << '\n';
            dict[root] = max(root->val + lwithout + rwithout, lwith + rwith);
        }
        return dict[root];
    }
};


// Another implementation - Hao Chen

class Solution {
public:
    int max(int a, int b) {
        return a > b ? a: b;
    }
    int max(int a, int b, int c) {
        return max(a, max(b,c));
    }
    int max(int a, int b, int c, int d) {
        return max(a, max(b, max(c,d)));
    }

    void rob_or_not(TreeNode* root, int& max_robbed, int& max_not_robbed) {
        // NULL room return 0;
        if (root == NULL) {
            max_robbed = max_not_robbed = 0;
            return ;
        }

        // we have two options, rob current room or not.
        int max_left_robbed, max_left_not_robbed;
        int max_right_robbed, max_right_not_robbed;
        rob_or_not(root->left, max_left_robbed, max_left_not_robbed);
        rob_or_not(root->right, max_right_robbed, max_right_not_robbed);

        // If root is robbed, then both left and right must not be robbed.
        max_robbed = root->val + max_left_not_robbed + max_right_not_robbed;

        // If root is not robbed, then 4 combinations are possible:
		//     left is robbed or not and right is either robbed or not robbed,
        max_not_robbed = max(max_left_robbed + max_right_robbed,
                             max_left_robbed + max_right_not_robbed,
                             max_left_not_robbed + max_right_robbed,
                             max_left_not_robbed + max_right_not_robbed);

    }
    int rob(TreeNode* root) {
        int robbed, not_robbed;
        rob_or_not(root, robbed, not_robbed);
        return max(robbed, not_robbed);
    }
};

/// Source : https://leetcode.com/problems/house-robber-iii/description/
/// Author : liuyubobobo
/// Time   : 2017-12-09

#include <iostream>
#include <map>

using namespace std;


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

/// Brute Force
/// Time Complexity: O(2^n), where n is the nodes' number in the tree
/// Space Complexity: O(h), where h is the tree's height
class Solution {

private:
    map<pair<TreeNode*, int>, int> dp;

public:
    int rob(TreeNode* root) {

        dp.clear();
        return rob(root, true);
    }

private:
    int rob(TreeNode* root, bool include){

        if(root == NULL)
            return 0;

        pair<TreeNode*, int> p = make_pair(root, include);
        if(dp.find(p) != dp.end())
            return dp[p];

        int res = rob(root->left, true) + rob(root->right, true);
        if(include)
            res = max(root->val + rob(root->left, false) + rob(root->right, false),
                       res);

        return dp[p] = res;
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber-iii/description/
/// Author : liuyubobobo
/// Time   : 2017-12-09

#include <iostream>
#include <map>

using namespace std;


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

/// Memory Search
/// Time Complexity: O(n), where n is the nodes' number in the tree
/// Space Complexity: O(n)
class Solution {

public:
    int rob(TreeNode* root) {
        return rob(root, true);
    }

private:
    int rob(TreeNode* root, bool include){

        if(root == NULL)
            return 0;

        int res = rob(root->left, true) + rob(root->right, true);
        if(include)
            res = max(root->val + rob(root->left, false) + rob(root->right, false),
                      res);

        return res;
    }
};

int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/house-robber-iii/description/
/// Author : liuyubobobo
/// Time   : 2017-12-09

#include <iostream>
#include <vector>

using namespace std;


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

/// Redefine the recursive function and return a two-element array
/// represent the include and exclude maximum result for robbing the node
///
/// Time Complexity: O(n), where n is the nodes' number in the tree
/// Space Complexity: O(1)
class Solution {

public:
    int rob(TreeNode* root) {
        vector<int> result = tryRob(root);
        return max(result[0], result[1]);
    }

private:
    vector<int> tryRob(TreeNode* root){

        if(root == NULL)
            return vector<int>(2, 0);

        vector<int> resultL = tryRob(root->left);
        vector<int> resultR = tryRob(root->right);
        vector<int> res(2, 0);

        res[0] = resultL[1] + resultR[1];
        res[1] = max(res[0], root->val + resultL[0] + resultR[0]);

        return res;
    }
};

int main() {

    return 0;
}