My iterative DP solution (C++)


  • 1
    A
    class Solution {
    public:
    
        
        vector<TreeNode *> generateTrees(int n) {
            if( n < 1 ) return vector< TreeNode *>(1);
            vector<TreeNode*> rootMem[ 100 ][ 100 ];// rootMem[ i ][ j ] stores the tree from j with length i
            for( int j = 0; j <= n + 1; j++ )           //Init. It should be noted that j = 0 and j = n + 1 must be inited
            {
                TreeNode * tmp = new TreeNode( j );
                rootMem[ 1 ][ j ].push_back( tmp );
                tmp = NULL;
                rootMem[ 0 ][ j ].push_back( tmp );
            }
            for( int i = 2; i <= n; i++ )//Length from 2 to n
            {
                for( int j = 1; j <= n - i + 1; j++ )// the smallest cannot exceed n - i + 1. n - i + 1  + i  -1 = n
                {
                    for( int k = 0; k < i; k++ )
                    {
                        for( int left = 0; left < rootMem[ k ][ j ].size(); left++ )
                        {
                            for( int right = 0; right < rootMem[ i - k - 1 ][ j + k + 1].size(); right++ )
                            {
                                TreeNode * tmp = new TreeNode( k + j );
                                tmp->left  = rootMem[ k ][ j ][ left ];
                                tmp->right = rootMem[ i - k - 1 ][ j + k + 1][ right ];
                                rootMem[ i ][ j ].push_back( tmp );
                            }
                        }
                    }
                }
            }
            return rootMem[ n ][ 1 ];
            
        }
    };

  • 0
    W

    Wow, thinking about this method must take you a lot of time: )


Log in to reply
 

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