Inefficient but simple java solution and improved solution


  • 0
    Z
    public class Solution {
        public int rob(TreeNode root) {
            if(root == null) return 0;
            return Math.max(root.val + helper(root.left,false) + helper(root.right,false), 
                            helper(root.left,true)+helper(root.right,true));
        }
        
        // flag = true means contains root 
        public int helper(TreeNode root,boolean flag) {
            if(root == null) return 0;
            if(flag) {
                return Math.max(root.val + helper(root.left,false) + helper(root.right,false), 
                            helper(root.left,true)+helper(root.right,true));
            }else {
                return helper(root.left,true)+helper(root.right,true);
            }
        }
    }
    
    // Improved solution
    public class Solution {
        public int rob(TreeNode root) {
            int[] res = new int[2];
            res = helper(root);
            return Math.max(res[0],res[1]);
        }
        public int[] helper(TreeNode root) {
            int[] res = new int[2];
            if(root == null) return res;
            int[] tmp1 = helper(root.left);
            int[] tmp2 = helper(root.right);
            // res[0] not contain root, res[1] contain root
            res[0] = Math.max(tmp1[0],tmp1[1]) +  Math.max(tmp2[0],tmp2[1]);
            res[1] = root.val + tmp1[0] + tmp2[0];
            return res;
        }
    }

Log in to reply
 

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