Simple Recursion Java Solution with Explanation


  • 14
    S

    The idea is to use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. The total number of distinct structure is their product. Thus, sum up the product for all numbers. Use a map to memorize the visited number.

    public class Solution {
        public int numTrees(int n) {
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(0,1);
            map.put(1,1);
            return numTrees(n, map);
        }
        
        private int numTrees(int n, Map<Integer, Integer> map){
            // check memory
            if(map.containsKey(n)) return map.get(n);
            // recursion
            int sum = 0;
            for(int i = 1;i <= n;i++)
                sum += numTrees(i-1, map) * numTrees(n-i, map);
            map.put(n, sum);
            return sum;
        }
    }

  • -1
    D

    Your solution works very slow, you should memoize the results that you've already calculated

    public class Solution {
        public int numTrees(int n) {
            // base case
            if(n <= 1){return 1;}
            if (memo[n] != -1) return memo[n];
            // recursion
            int sum = 0;
            for(int i = 1;i <= n;i++)
                sum += numTrees(i-1-0) * numTrees(n-i);
            return memo[n] = sum;
        }
    }

  • 0
    D

    By the way, this formula known as Catalan numbers formula as well


  • 0
    J

    but int case, numTree(0), it should be 0 i think.. because it has the limitation of 1 ~ n ...doesn't matter to this case as if the case 0 been paid attention


  • 0
    V

    I submit the same code as you and time limit exceeded when n = 19.


  • 0
    S

    Thank you for pointing it out. It seems the test case was changed afterwards. The original DFS solution will run in O(2^n) time. When apply path memorizing, the DFS will run in O(n^2) time. Please see the updated code. Hope that helps!


  • 0
    V

    I see, thank you for your reply.


  • 0
    Y

    share my similar solution.

        private int[] counts = null;
        
        public int numTrees(int n) {
            counts = new int[1 + n];    
            return calNumTrees(n);
        }
        
        private int calNumTrees(int n) {
            if (counts[n] != 0) return counts[n];   // cache
            
            if (n <= 1) return 1;
            
            int total = 0;
            for (int i = 1; i <= n; ++i) {
                total += calNumTrees(i - 1) * calNumTrees(n - i);
            }
            counts[n] = total;
            
            return total;
        }
    

Log in to reply
 

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