Easy to Understand 1 ms Java solution using recursion with proper comments


  • 0
    V
    public int rob(TreeNode root) {
            int[] result = robUtils(root);
            return Math.max(result[0],result[1]);
        }
        /**
        * returns integer array whose 0 index will be max value till root and 1st index will be max value till roots child. 
         */
        public int[] robUtils(TreeNode root){
            int[] result = new int[2]; // default value of each element is 0
            if( root != null ){
                int[] resultLeft = robUtils(root.left);
                int[] resultRight = robUtils(root.right);
                // result[1] will contain sum of max values of left and right sub trees.
                result[1] = Math.max(resultLeft[0],resultLeft[1]) + Math.max(resultRight[0],resultRight[1]);
                // result[0] will contain sum of current value plus the alternate maximum of left and right child i.e resultLeft[1] and resultRight[1].
                result[0] = root.val + resultLeft[1] + resultRight[1];
            }
            return result;
        }

Log in to reply
 

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