Simple Java Solution


  • 0
    J

    We are looking for the number of sorted binary trees we can build with n elements. The word tree already implicates recursion (because of subtrees).
    We now have n possible numbers which can be the root i of the tree, for all of them we have to find the number of different subtrees on the left and right. The combination of those are the number of possible binary trees with r as the root. So all we do now is sum up the possibilities for all elements i in the list [1..n]
    Of course this algorithm can be tuned a bit as there is a bit of symmetry there but I haven't done so...

    public int numTrees(int n) {
            if (n <= 1)
                return 1;
            if (n == 2)
                return 2;
            int poss = 0;
            for(int i = 1; i <= n; i++) {
                poss += numTrees(i - 1)*numTrees(n - i);
            }
            return poss;
        }
    

Log in to reply
 

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