95. Unique Binary Search Trees II(构建唯一二叉树）

骑猪看日落 2022-11-25 13:23 106阅读 0赞

给定一个整数n，生成存储值1 … n的所有结构唯一的BST（二进制搜索树） 。

例：

输入： 3  
输出：  
\[  
\[1，null，3,2\]，  
\[3,2，null，1\]，  
\[3,1，null，null，2\]，  
\[2,1,3\]，  
\[1，null，2，null，3\]  
\]  
Input: 3  
Output:  
\[  
\[1,null,3,2\],  
\[3,2,null,1\],  
\[3,1,null,null,2\],  
\[2,1,3\],  
\[1,null,2,null,3\]  
\]  
Explanation:  
The above output corresponds to the 5 unique BST’s shown below:

1 3 3 2 1  
\\ / / / \\  
3 2 1 1 3 2  
/ / \\  
2 1 2 3

思路：  
将1-n的数字构建成唯一 **二叉搜索树**，将所有的情况放入结果集返回。  
思路，将遍历每个元素，并且将每个节点都作为根节点进行分成左右子树节点集合。然后遍历两个左右集合，分别设置该root节点的左右节点来进行设置。然后压入res数组中

code

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    class Solution { 
    public:
        vector<TreeNode*> generateTrees(int n) { 
            if (n==0)   return vector<TreeNode*> ();
            return genTrees(1,n);
        }
        vector<TreeNode*> genTrees(int start,int end)
        { 
            vector<TreeNode*> res;
            if(start>end)
            { 
                res.push_back(NULL);
                return res;
            }
            else if(start==end)
            { 
                res.push_back(new TreeNode(start));
                return res;
            }
            vector<TreeNode*>left,right;
            for(int i=start;i<=end;i++)
            { 
                left = genTrees(start,i-1);
                right = genTrees(i+1,end);
                for (auto lnode : left)
                { 
                    for(auto rnode : right)
                    { 
                        TreeNode* root = new TreeNode(i);
                        root->left = lnode;
                        root->right = rnode;
                        res.push_back(root);
                    }
                }
            }
            return res;
        }
    };