Share my C++ solution, easy to understand


  • 0
    V
    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            if (n < 1)
                return vector<TreeNode*> (0);
                
            return generate_tree_help(1, n);
        }
        
        vector<TreeNode*> generate_tree_help(int start, int end)
        {
            vector<TreeNode*> ret;
            
            if (start > end)
            {
                ret.push_back(NULL);
                return ret;
            }
                
            for (int i = start; i <= end; i++)
            {
                vector<TreeNode*> left_subtree = generate_tree_help(start, i-1);
                vector<TreeNode*> right_subtree = generate_tree_help(i+1, end);
                
                int left_size = left_subtree.size();
                int right_size = right_subtree.size();
                
                for  (int l = 0; l < left_size; l++)
                {
                    for (int r = 0; r < right_size; r++)
                    {
                        TreeNode *root = new TreeNode(i);
                        
                        root->left = left_subtree[l];
                        root->right = right_subtree[r];
                        
                        ret.push_back(root);
                    }
                }
            }
            
            return ret;
        }
    };
    

Log in to reply
 

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