Java 1ms solution using dynamic programming w/ explanation.


  • 0
    A
    public class Solution {
        public int rob(TreeNode root) {
            if(root == null)
                return 0;
            
            passTree(root);
            
            return root.val;
        }
        
        //The ideia is to do a DP in the tree, from the bottom to the top (the value of the DP is stored in each node, in the variable val). We should find out which one of the two possible processes gives us the better outcome: To ignore the current node and sum the dp of left and right nodes of our current node or to consider the current node and sum the dp of the children of the left node and right node of our current one.
        
        public void passTree(TreeNode node)
        {
            if(node == null)
                return;
                
            passTree(node.left);
            passTree(node.right);
            
            int firstCalculation = 0;
            
            int temp = (node.left == null) ? 0 : node.left.val;
            firstCalculation += temp;
            temp = (node.right == null) ? 0 : node.right.val;
            firstCalculation += temp;
            
            int secondCalculation = 0;
            if(node.left != null)
            {
                temp = (node.left.left == null) ? 0 : node.left.left.val;
                secondCalculation += temp;
                temp = (node.left.right == null) ? 0 : node.left.right.val;
                secondCalculation += temp;
            }
            
            if(node.right != null)
            {
                temp = (node.right.left == null) ? 0 : node.right.left.val;
                secondCalculation += temp;
                temp = (node.right.right == null) ? 0 : node.right.right.val;
                secondCalculation += temp;
            }
            
            node.val = Math.max(firstCalculation, node.val + secondCalculation);
        }
    }
    

Log in to reply
 

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