Recursive solution using Java, fast and easy to understand


  • 0

    I redefine a node to wrap the original treenode.
    Look, here are two situations, the robber will rob this house or not, that is withval or withoutval in the new class node. And we can use a recursive solution to count the with or without val from the bottom of the tree. Just remember if the robber rob this house, the left and right node can't be robbed both, however if the robber don't rob this house, the left and right CAN be robbed or not.

    public class Solution {
        public class Node {
            int val;
            TreeNode left;
            TreeNode right;
            int withval;
            int withoutval;
            Node(TreeNode node, int withval, int withoutval) {
                this.val = node.val;
                this.left = node.left;
                this.right = node.right;
                this.withval = withval;
                this.withoutval = withoutval;
            }
        }
        
        public int rob(TreeNode root) {
            if(root == null) return 0;
            Node n = new Node(root,0,0);
            return Math.max(robhelp(n).withval, robhelp(n).withoutval);
        }
        
        public Node robhelp(Node root) {
            if(root == null) return null;
            else if(root.left == null && root.right == null) {
                root.withoutval = 0;
                root.withval = root.val;
            }
            else if(root.left == null) {
                Node right = robhelp(new Node(root.right,0,0));
                root.withoutval = Math.max(right.withval,right.withoutval) ;
                root.withval = right.withoutval + root.val;
            }
            else if(root.right == null) {
                Node left = robhelp(new Node(root.left,0,0));
                root.withoutval = Math.max(left.withval,left.withoutval);
                root.withval = left.withoutval + root.val;
            }
            else {
                Node left = robhelp(new Node(root.left,0,0));
                Node right = robhelp(new Node(root.right,0,0));
                root.withval = left.withoutval + right.withoutval + root.val;
                int m1 = left.withval + right.withval;
                int m2 = left.withoutval + right.withval;
                int m3 = left.withval + right.withoutval;
                int m4 = left.withoutval + right.withoutval;
                root.withoutval = Math.max(Math.max(Math.max(m1,m2),m3),m4);
            }
            return root;
        }
    }
    
    

Log in to reply
 

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