DP solution with a different explanation


  • 0
    S

    conclusion:the number of different BST of n nodes =the number of different shapes of binary tree of n nodes
    if a BST is like this:
    A
    ...\
    .....B
    ..../
    ..C
    we can know the inorder traversal is A C B
    if the values of this tree is 1,2,3.then A=1 C=2 B=3 definitely
    so we can see:once we have decided the shape of the BST,then we can put [1,2,...,n] to this tree in just one method.
    so the problem becomes how many shapes are there for n nodes?
    for this problem,suppose the we have a root node,then we can assume the left subtree has x nodes(0<=x<=n-1),so the right subtree has n-x nodes
    using dp[i] to represent the number of shapes for a binary tree of i nodes
    dp[i]=sigma{dp[j]*dp[i-1-j] | 0<=j<=i-1} this means when we give j nodes to the left subtree,then the number of different shapes of the whole tree =the number of different shapes of the left subtree * the number of different shapes of the right subtree.and obviously,we can give 0,1,2,...,i-1 nodes to the left subtree.

    class Solution {
    public:
        int numTrees(int n) {
            int i,j;
            vector<int> dp(n+1);
            dp[0]=1;dp[1]=1;
            for(i=2;i<=n;i++)
                for(j=0;j<=i-1;j++)
                    dp[i]+=dp[j]*dp[i-1-j];
            return dp[n];
        }
    };
    

Log in to reply
 

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