Clean Java solution (easy to understand)


  • 1
    J
    class RobValue{
        int value1; // the total value with current house
        int value2; // the total value without current house
        RobValue(int a, int b){
            value1 = a;
            value2 = b;
        }
    }
    
    public int rob(TreeNode root) {
        RobValue value = calculateRobValue(root);
        return Math.max(value.value1, value.value2);
    }
    
    private RobValue calculateRobValue(TreeNode root)
    {
        RobValue result = new RobValue(0, 0);
        if (root == null) return result;
        
        RobValue leftValue = calculateRobValue(root.left);
        RobValue rightValue = calculateRobValue(root.right);
        
        result.value1 = root.val + leftValue.value2 + rightValue.value2;
        result.value2 = Math.max(leftValue.value1, leftValue.value2) + Math.max(rightValue.value1, rightValue.value2);
        
        return result;
    }

  • 0
    J

    For each node, you only need to calculate the two values: value with current node, and value without current node.

    When doing this and passing the value up, you will find that you have everything you need to solve the problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.