SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is about maximizing the amount of money that can be robbed from a binary tree. In this tree, each node represents a house with a certain amount of money. The robber can't rob two directly connected houses (parent-child relationship), so we need to maximize the money without robbing two connected houses.

Intuition

The core of the problem lies in determining the optimal strategy for robbing nodes in a binary tree such that no two adjacent nodes are robbed. This can be broken down into a decision: for each node, either rob it (and avoid robbing its children) or don’t rob it (allowing its children to be robbed).

The intuition is that for every node, we have two options:

• Rob this node, but we can't rob its direct children.
• Don’t rob this node, and we can take the maximum of robbing or not robbing its children.

Approach

1. Perform a depth-first search (DFS) to traverse the tree.
2. For each node, calculate two possible values:
   • withRoot: the maximum amount of money we can rob if we rob this node (which means we can't rob its children).
   • withoutRoot: the maximum amount of money we can rob if we don’t rob this node (which means we can consider robbing its children).
3. At each node, return an array where the first value is the maximum amount when robbing the current node and the second value is the maximum when not robbing it.
4. At the root, return the maximum of these two values.

Complexity

Time Complexity:

O(N), where N is the number of nodes in the binary tree. Each node is visited once.

Space Complexity:

O(H), where H is the height of the tree due to the recursion stack. In the worst case, the height could be N (for a skewed tree), but in a balanced tree, it would be log(N).

Code

C++

/**
 * 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:
    vector<int> dfs(TreeNode* root) {
        if (!root) return {0, 0};

        vector<int> left = dfs(root->left);
        vector<int> right = dfs(root->right);

        int withRoot = root->val + left[1] + right[1];
        int withoutRoot = max(left[0], left[1]) + max(right[0], right[1]);

        return {withRoot, withoutRoot};
    }
    
    int rob(TreeNode* root) {
        vector<int> result = dfs(root);
        return max(result[0], result[1]);
    }
};

Python

# 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 dfs(self, root):
        if not root:
            return [0, 0]

        left = self.dfs(root.left)
        right = self.dfs(root.right)

        with_root = root.val + left[1] + right[1]
        without_root = max(left) + max(right)

        return [with_root, without_root]

    def rob(self, root: TreeNode) -> int:
        return max(self.dfs(root))

Java

/**
 * 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 int[] dfs(TreeNode root) {
        if (root == null) return new int[]{0, 0};

        int[] left = dfs(root.left);
        int[] right = dfs(root.right);

        int withRoot = root.val + left[1] + right[1];
        int withoutRoot = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        return new int[]{withRoot, withoutRoot};
    }
    
    public int rob(TreeNode root) {
        int[] result = dfs(root);
        return Math.max(result[0], result[1]);
    }
}

JavaScript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var rob = function(root) {
    const dfs =(root)=>{

        if(!root)return [0,0]

        const left = dfs(root.left);

        const right = dfs(root.right);

        const withRoot = root.val+left[1]+ right[1];

        const withoutRoot = Math.max(...left) + Math.max(...right);

        return [withRoot, withoutRoot];
    }
   
    return Math.max(...dfs(root));
};