My simple Java recursive solution


  • 9
    public class Solution {
        public int rob(TreeNode root) {
            if(root==null) return 0;
            if(root.left==null&&root.right==null) return root.val;
            
            int left=0, right=0;
            int subleft=0, subright=0;
        
        if(root.left!=null){
            left=rob(root.left);
            subleft=rob(root.left.left)+rob(root.left.right);
        }
        
        if(root.right!=null){
            right=rob(root.right);
            subright=rob(root.right.left)+rob(root.right.right);
        }
        
        int sum1=left+right;
        int sum2=subleft+subright+root.val;
        
        return (sum1>sum2)?sum1:sum2;
    }
    

    }


  • 0
    J

    best solution!


  • 0
    S

    Awesome solution!!


  • 0

    Upvoted. simple and easy to understand. Look like a DFS recursion + memorization solution.

    But if I were the interviewer I might give a follow up quesiton: what if this is a tree, rather than a binary tree.


Log in to reply
 

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