A bottom-up DP solution and a top-down recursive solution.


  • 0
    A

    Top-down recursive solution

    class Solution(object):
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n == 0: return []
            return self.helper(1,n)
        
        def helper(self, i, j):
            if i > j:
                return [None]
            
            res = []
            for n in xrange(i, j+1):
                left_nodes = self.helper(i, n-1)
                right_nodes = self.helper(n+1, j)
                for left_node in left_nodes:
                    for right_node in right_nodes:
                        node = TreeNode(n)
                        node.left = left_node
                        node.right = right_node
                        res.append(node)
        
            return res
    

    Bottom-up DP

    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            if (n==0) return {};
            
            vector<vector<vector<TreeNode*>>> dp(n+2, vector<vector<TreeNode*>>(n+2));
            
            
            
            for (int i=0; i<=n+1; ++i)
                for (int j=0; j<=n+1; ++j)
                    if (i > j)
                        dp[i][j].push_back(nullptr);
            
            
            for (int len = 1; len <= n; ++len) {
                
                for (int i = 1; i <= n - len + 1; ++i) {
                    int j = i+len-1;
                    for (int k = i; k <= j; k++) {
                        for (auto &l: dp[i][k-1]) {
                            for (auto &r: dp[k+1][j]) {
                                auto node = new TreeNode(k);
                                node->left = l;
                                node->right = r;
                                dp[i][j].push_back(node);
                            }
                        }  
                    }                
                }
            }
            
            return dp[1][n];
        }
    };
    

Log in to reply
 

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