DP solution with a different explanation

  • 0

    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:
    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 {
        int numTrees(int n) {
            int i,j;
            vector<int> dp(n+1);
            return dp[n];

Log in to reply

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