A java 2ms O(n) recursion solution without HashMap.


  • 0
    B

    In each recursion, you should know:

    1. value of current root's children
    2. value of current root's grandchildren

    And choose the max value between
    case 1: current root with grandchildren
    case 2: children.

    Pay attention to when you consider case2, you can pick max of children's children and children's grandchildren. Due to in each recursion, we should return 2 values, so we use an extra class Cell to wrap the 2 values. And here is the code:

        int max = 0;
        public int rob(TreeNode root) {
            if(root == null) return 0;
            helper(root);
            return max;
        }
        
        private Cell helper(TreeNode root){
            if(root == null)
                return new Cell(0, 0);
            
            Cell left = helper(root.left);
            Cell right = helper(root.right);
            
            int withRoot = root.val + left.grandchildren + right.grandchildren;
            //when you handle case without Root, you can pick either root's children or root's grandchildren
            int withoutRoot = Math.max(left.children, left.grandchildren) + Math.max(right.children, right.grandchildren);
            max = Math.max(withRoot, withoutRoot);
            return new Cell(withRoot, withoutRoot);
        }
    }
    
    class Cell{
        int children;
        int grandchildren;
        
        public Cell(int children, int grandchildren){
            this.children = children;
            this.grandchildren = grandchildren;
        }
    }

Log in to reply
 

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