House Robber III

class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        ArrayList<Integer> values = new ArrayList<>();
        HashMap<Integer, ArrayList<Integer>> nodeChildren = new HashMap<>();
        nodeChildren.put(-1, new ArrayList<>());
        int idx = -1;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        Queue<Integer> indexQueue = new LinkedList<>();
        indexQueue.add(idx);

        while (!nodeQueue.isEmpty()) {
            TreeNode curr = nodeQueue.poll();
            int parentIdx = indexQueue.poll();
            if (curr != null) {
                idx++;
                values.add(curr.val);
                nodeChildren.put(idx, new ArrayList<>());
                nodeChildren.get(parentIdx).add(idx);

                nodeQueue.add(curr.left);
                indexQueue.add(idx);
                nodeQueue.add(curr.right);
                indexQueue.add(idx);
            }
        }

        int[] robCurrent = new int[idx + 1];
        int[] noRobCurrent = new int[idx + 1];

        for (int i = idx; i >= 0; i--) {
            ArrayList<Integer> children = nodeChildren.get(i);
            if (children.isEmpty()) {
                robCurrent[i] = values.get(i);
                noRobCurrent[i] = 0;
            } else {
                robCurrent[i] = values.get(i);
                for (int child : children) {
                    robCurrent[i] += noRobCurrent[child];
                    noRobCurrent[i] += Math.max(robCurrent[child], noRobCurrent[child]);
                }
            }
        }

        return Math.max(robCurrent[0], noRobCurrent[0]);
    }
}

The given Java solution effectively tackles the problem of maximizing the amount of money robbers can steal from a house, represented as a binary tree structure where values at each node represent the potential loot at each house. Here's a concise summary of how the solution operates:

• First, the solution method checks if the tree is empty. If it is, it returns zero.
• Utilizes two main data structures: ArrayList<Integer> to store the values of each node, and HashMap<Integer, ArrayList<Integer>> for tracking the indices of node children.
• Leverages breadth-first traversal with the help of queues to create an indexed representation of the binary tree. This is done by storing values by level and noting parent-child relationships.
• With the tree represented in indexed form, two arrays (robCurrent and noRobCurrent) are created to handle dynamic programming decisions. The first array stores the maximum possible loot when the current node is robbed, and the second when it is not.
• Fills these dynamic programming arrays in a bottom-up manner. It ensures that on robbing a node, the children nodes cannot be robbed, and the maximum loot includes the greater value of robbing or not robbing the node’s children.
• Finally, the solution returns the maximum of the values in robCurrent and noRobCurrent for the root node, determining the optimal strategy to maximize the loot.

This approach cleverly combines tree traversal with dynamic programming principles, ensuring an efficient and effective solution to the problem.

class Solution:
    def steal(self, root: TreeNode) -> int:
        if not root:
            return 0

        # Convert tree to list representation
        vals_list = []
        tree_dict = {-1: []}
        node_index = -1
        nodes_queue = [(root, -1)]
        while nodes_queue:
            current_node, parent_idx = nodes_queue.pop(0)
            if current_node:
                node_index += 1
                vals_list.append(current_node.val)
                tree_dict[node_index] = []
                tree_dict[parent_idx].append(node_index)
                nodes_queue.append((current_node.left, node_index))
                nodes_queue.append((current_node.right, node_index))

        # maximum profit when robbing the current node
        max_rob = [0] * (node_index + 1)

        # maximum profit without robbing the current node
        max_not_rob = [0] * (node_index + 1)

        for idx in reversed(range(node_index + 1)):
            if not tree_dict[idx]:  # if it's a leaf
                max_rob[idx] = vals_list[idx]
                max_not_rob[idx] = 0
            else:
                max_rob[idx] = vals_list[idx] + sum(max_not_rob[child] for child in tree_dict[idx])
                max_not_rob[idx] = sum(max(max_rob[child], max_not_rob[child]) for child in tree_dict[idx])

        return max(max_rob[0], max_not_rob[0])

The "House Robber III" problem involves maximizing the amount of money you can rob from a binary tree, where adjacent nodes (direct parent-child relationships) cannot both be robbed. The Python solution provided uses dynamic programming to address this challenge.

• Implement the steal method, which operates on a binary tree structure defined by TreeNode. The method returns an integer representing the maximum amount you can steal without triggering adjacent alarms.

• Begin by checking if the root is None; if true, return 0, indicating there's nothing to rob.

• Convert the binary tree into a list and dictionary representation for easier access and manipulation during dynamic programming calculations. Use a breadth-first search (BFS) to populate vals_list with node values and tree_dict with parent-child relationships.

• Establish two arrays, max_rob and max_not_rob. The max_rob array holds the maximum profit possible when robbing the corresponding node, and the max_not_rob array holds the maximum profit when not robbing the node.

• Iterate from the bottom of the tree (leaf nodes) up to the root. For leaf nodes, directly assign the node's value to max_rob and set max_not_rob to 0. For non-leaf nodes, calculate the max_rob by adding the node's value to the sum of max_not_rob values for its children. Calculate max_not_rob as the sum of the maximum values between max_rob and max_not_rob of the children nodes.

• Ultimately, return the maximum value between max_rob[0] and max_not_rob[0], which represents the best strategy's profit when starting from the root of the tree.

This method ensures efficiency by reducing the complex tree structure to lists and optimally calculating the potential profit using dynamic programming, thereby ensuring that the solution scales well with larger trees.