Did you deduce a formula of the tree numbers f(n) or just simulate a tree generation process?


  • 2
    B

    i simulate a BST generation, and got TLE.


  • 0

    You should probably explain more how you simulate your BST generation. As far as I knew, you are not required to deduce the formula in order to get Accepted.


  • 7
    S

    You need to use formula with recursion to calculate the number without exceeding.
    Check: http://cs.lmu.edu/~ray/notes/binarytrees/

    You should not need to simulate entire BST generation.
    That will be done for part II.


  • 29
    A

    Simulation is not necessary

    Even recursive function can pass, test cases are too weak!

    idea:
    choose i to be the root, then there i -1 numbers in the left child tree, n - i numbers in the right child tree, calculate child tree recursively

    f(0) = 1

    f(1) = 1

    f(2) = 2

    f(n) = f(n-1) * f(1 -1) + f(n-2) * f(2 -1) + f(n-3) * f(3-1) + ... + f(n-n) * f(n-1)

    In addition, lookup table can be used to improve performance!


  • 6
    L

    Consider about Catalan Number.


  • 0
    R

    Yes I had the same idea. I memoize results for i = 1...n and in every iteration I uses memoized values from former steps.


  • 9
    L
    class Solution {
    public:
        int numTrees(int n) {
            long long ans = 1;
            for(int i = 1; i <= n; ++ i)
                ans  = ans * 2 * (2 * i - 1) / (i + 1);
            return (int) ans;
        }
    }; 
    

    It is base on the iterative formula of Catalan number.
    C(i+1) = C(i) * 2 * ( 2 * i - 1 ) / (i + 1);


  • 0
    R

    of course we dont need, it is not about memorization


Log in to reply
 

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