lintcode 164. 不同的二叉查找树 II

深藏阁楼爱情的钟 2023-07-07 12:39 10阅读 0赞

给出n，生成所有由1…n为节点组成的不同的二叉查找树

样例
    样例 1:
    
    输入:3
    输出:
        1         3     3       2    1
         \       /     /       / \    \
          3     2     1       1   3    2
         /     /       \                \
        2     1         2                3
    注意事项
    n>=1

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    class Solution {
        
    public:
        /**
         * @paramn n: An integer
         * @return: A list of root
         */
        vector<TreeNode *> generateTrees(int n) {
        
            // write your code here
            return dfs(1,n);
        }
        vector<TreeNode*>dfs(int start,int end)
        {
        
            vector<TreeNode*> tmp;
            if(start>end)
            {
        
                tmp.push_back(NULL);
                return tmp;
            }
            else
            {
        
                for (int i = start; i <= end; i++) {
        
                    vector<TreeNode*>left=dfs(start,i-1);
                    vector<TreeNode*>right=dfs(i+1,end);
                    for (auto lnode : left) {
        
                        for(auto rnode : right)
                        {
        
                            TreeNode*node=new TreeNode(i);
                            node->left=lnode;
                            node->right=rnode;
                            tmp.push_back(node);
                        }
                    }
                }
            }
            return tmp;
        }
    };