Two solutions with Java (1 ms)


  • 2
    S
    public int rob(TreeNode root) {
        if(root==null) return 0;
        rob1(root);
        return root.val;
    }
    public int rob1(TreeNode root){
        if(root==null) return 0;
        int pre=0;
        root.val+=rob1(root.left)+rob1(root.right);
        if(root.left!=null)  pre+=root.left.val;
        if(root.right!=null)  pre+=root.right.val;
        root.val=Math.max(pre,root.val);
        return pre;
    }
    

    The other solution need extra class:

    class Profit{
       int preprofit;
       int maxprofit;
       Profit(int pre,int max){
           preprofit=pre;
           maxprofit=max;
       }
    }
    public class Solution {
         public int rob(TreeNode root ) {
              return rob1(root).maxprofit;
         }
         public Profit rob1(TreeNode root){
               if (root == null) return new Profit(0, 0);
               int pre = 0, max = root.val;
               Profit left = rob1(root.left), right = rob1(root.right);
               max += left.preprofit + right.preprofit;
               pre = left.maxprofit + right.maxprofit;
               max = Math.max(pre,max);
               return new Profit(pre,max);
         }
    }

  • 0

    nice and simple solution. I tried the same but having some issues..


  • 0
    R

    Don't like this solution since it modified the original tree:
    ...
    root.val += rob1(root.left)+rob1(root.right);
    ...
    root.val = Math.max(pre,root.val);
    ...


  • 0
    C

    Agree. Another option could be making a copy of the original tree and modifying the copied tree.


  • 0
    S

    I have added a new solution


  • 0
    R

    Don't need copy the original tree, just need some data structure to save the middle result like the OP added recently. I did in a similar way but just use a 2-element array.


Log in to reply
 

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