Easy to understand(java)


  • 17
    S

    public class Solution {

    public int rob(TreeNode root) {
        if (root == null) return 0;
        return Math.max(robInclude(root), robExclude(root));
    }
    
    public int robInclude(TreeNode node) {
        if(node == null) return 0;
        return robExclude(node.left) + robExclude(node.right) + node.val;
    }
    
    public int robExclude(TreeNode node) {
        if(node == null) return 0;
        return rob(node.left) + rob(node.right);
    }
    

    }


  • 1
    Z

    Here is the relations:


  • 0
    N
    This post is deleted!

  • 0
    Y

    @siyuan10 quite straightforward solution, very easy to understand.


  • 0
    L

    I think my solution is as same as yours. I only use one function, just add a parameter to distingush robInclude and robExclude. But I got TLE. Can anyone tell me why?

    	public int rob(TreeNode root) {
    		int robTrue=rob(root,true);
    		int robFalse=rob(root, false);
    		if(robTrue>=robFalse){
    			return robTrue;
    		}
    		else{
    			return robFalse;
    		}
    	}
    	
    	public int rob(TreeNode node,boolean canRob){
    		if(node==null){
    			return 0;
    		}
    		int rob=0;
    		if(canRob==true){
    			rob+=node.val+rob(node.left,false)+rob(node.right,false);
    		}
    		else{
    			int leftMax=Math.max(rob(node.left,true), rob(node.left,false));
    			int rightMax=Math.max(rob(node.right,true), rob(node.right,false));
    			rob+=(leftMax+rightMax);
    		}
    		return rob;
    	}
    

Log in to reply
 

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