House Robber Iii

                                            
/**
 * 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:
    int rob(TreeNode* root) {
        if (!root) return 0;
        
        pair<int, int> result = helper(root);
        
        return max(result.first, result.second);
    }
    
    pair<int, int> helper(TreeNode* node) {
        if (!node) return {0, 0};
        
        pair<int, int> left = helper(node->left);
        pair<int, int> right = helper(node->right);
        
        int rob_current = node->val + left.second + right.second;
        int not_rob_current = max(left.first, left.second) + max(right.first, right.second);
        
        return {rob_current, not_rob_current};
    }
};

                                            
/**
 * 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 {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int[] result = robSub(root);
        
        return Math.max(result[0], result[1]);
    }
    
    private int[] robSub(TreeNode node) {
        if (node == null) {
            return new int[2];
        }
        
        int[] left = robSub(node.left);
        int[] right = robSub(node.right);
        
        int[] result = new int[2];
        result[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        result[1] = node.val + left[0] + right[0];
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 */
public class Solution {
    public int Rob(TreeNode root) {
        if(root == null){
            return 0;
        }
        
        int[] result = RobSub(root);
        return Math.Max(result[0], result[1]);
    }
    
    private int[] RobSub(TreeNode root){
        if(root == null){
            return new int[2];
        }
        
        int[] left = RobSub(root.left);
        int[] right = RobSub(root.right);
        
        int[] result = new int[2];
        result[0] = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
        result[1] = root.val + left[0] + right[0];
        
        return result;
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 */
var rob = function(root) {
    function dfs(node) {
        if (node === null) {
            return [0, 0];
        }
        const left = dfs(node.left);
        const right = dfs(node.right);
        const steal = node.val + left[1] + right[1];
        const skip = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [steal, skip];
    }
    
    const result = dfs(root);
    return Math.max(result[0], result[1]);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
function rob(root: TreeNode | null): number {
    function robHelper(node: TreeNode | null): [number, number] {
        if (!node) {
            return [0, 0];
        }
        
        const left = robHelper(node.left);
        const right = robHelper(node.right);
        
        const robCurr = node.val + left[1] + right[1];
        const notRobCurr = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        
        return [robCurr, notRobCurr];
    }
    
    const result = robHelper(root);
    return Math.max(result[0], result[1]);
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer
     */
    function rob($root) {
        $result = $this->helper($root);
        return max($result[0], $result[1]);
    }
    
    function helper($node) {
        if ($node == null) {
            return [0, 0];
        }
        
        $left = $this->helper($node->left);
        $right = $this->helper($node->right);
        
        $rob = $node->val + $left[1] + $right[1];
        $notRob = max($left[0], $left[1]) + max($right[0], $right[1]);
        
        return [$rob, $notRob];
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func rob(root *TreeNode) int {
    result := robHelper(root)
    return max(result[0], result[1])
}

func robHelper(node *TreeNode) [2]int {
    if node == nil {
        return [2]int{0, 0}
    }

    left := robHelper(node.Left)
    right := robHelper(node.Right)

    rob := node.Val + left[1] + right[1]
    noRob := max(left[0], left[1]) + max(right[0], right[1])

    return [2]int{rob, noRob}
}

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

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right

def rob(root)
    def helper(node)
        return [0, 0] if node.nil?
        
        left = helper(node.left)
        right = helper(node.right)
        
        rob_current = node.val + left[1] + right[1]
        not_rob_current = [left[0], left[1]].max + [right[0], right[1]].max
        
        [rob_current, not_rob_current]
    end
    
    result = helper(root)
    result.max
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null)
 */

object Solution {
    def rob(root: TreeNode): Int = {
        def robSub(root: TreeNode): Array[Int] = {
            if (root == null) return Array(0, 0)
            val left = robSub(root.left)
            val right = robSub(root.right)
            Array(Math.max(left(0), left(1)) + Math.max(right(0), right(1)), root.value + left(0) + right(0))
        }
        val res = robSub(root)
        Math.max(res(0), res(1))
    }
}

To solve this coding challenge, we need to focus on the structure and properties of the binary tree, and how to maximize the amount of money the thief can rob without alerting the police. The challenge essentially involves performing a Depth-First Search (DFS) and using dynamic programming at each node to decide whether to rob the current house or not.

Explanation

Problem Breakdown

Each house is represented as a node in a binary tree.
Robbing two directly-linked houses is not allowed as it will alert the police.
You need to maximize the amount of money stolen.

Strategy

We will use a combination of recursion and dynamic programming to solve this problem. The idea is to use DFS to traverse the tree and calculate the maximum amount of money that can be robbed along the way. At each node, we have two choices:

Rob the current house (node), which means we cannot rob its direct children nodes.
Do not rob the current house, which means we can consider robbing its children.

We will create a helper function

dfs(node)

which returns two values in a tuple/list:

The maximum money that can be robbed if we rob the current house.
The maximum money that can be robbed if we skip the current house.

Detailed Steps in Pseudocode

Base Case :

If the node is
null

, return
[0, 0]

because no money can be robbed.

Recursive Case :

Recursively call
dfs

for the left and right child.
Calculate
rob_this_node

as the sum of node's value plus the amount of money that can be robbed from the children nodes when they are skipped.
Calculate
skip_this_node

as the sum of the maximum values from both left and right children, considering they might be robbed or skipped.

Final Decision :

After the DFS traversal completes, the root will have two possible values:
rob_this_node

and
skip_this_node

.
The result will be the maximum of these two values.

Below is the detailed Pseudocode with comments:

                                            
# TreeNode definition for reference
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Main function to initiate the robbing process
function rob(root):
    # Helper function to perform DFS and calculate maximum rob amount
    function dfs(node):
        # If node is null, return [0, 0] as no money can be robbed
        if node == null:
            return [0, 0]
        
        # Perform DFS on the left child
        left = dfs(node.left)
        # Perform DFS on the right child
        right = dfs(node.right)
        
        # Calculate the amount if we rob this node
        rob_this_node = node.val + left[1] + right[1]
        
        # Calculate the amount if we skip this node
        skip_this_node = max(left[0], left[1]) + max(right[0], right[1])
        
        # Return both scenarios
        return [rob_this_node, skip_this_node]
    
    # Perform DFS starting from the root
    result = dfs(root)
    # The final result will be the maximum of robbing or skipping the root node
    return max(result[0], result[1])

Explanation of Variables:

node

: Current node in the binary tree.
left

/
right

: Results from the left and right subtrees, respectively.
rob_this_node

: Maximum amount of money if we rob the current node.
skip_this_node

: Maximum amount of money if we skip the current node.
result

: Final results of maximum money that can be robbed from the root node.

Base Case:

When the node is
null

, return
[0, 0]

because there are no houses to rob.

Recursive Case:

For
rob_this_node

, add the value of the current node to the sums from left and right subtrees assuming their direct children weren't robbed (i.e.,
left[1]

and
right[1]

).
For
skip_this_node

, add the maximum money that can be obtained from either robbing or skipping the children (i.e.,
max(left[0], left[1])

+
max(right[0], right[1])

).

By using this approach, the solution leverages the structure of the tree and ensures maximum potential robbery without setting off the alarm that comes from robbing two directly linked houses.