首页 > 代码库 > leetcode Unique Binary Search Trees II

leetcode Unique Binary Search Trees II

和上一题Unique Binary Search Trees 一样,这里是要记录所有的可能。存在树里面。

这题还是有点难的,我拿了笔写了前几个,推敲了一下,发现如果和上一题一样,存前面的值计算后面的的话会非常复杂,且可能涉及到给一颗数的所有节点加某个值。最终还是放弃用这个方法。

可行的二叉查找树的数量是相应的卡特兰数,不是一个多项式时间的数量级,所以我们要求解所有的树,自然是不能多项式时间内完成的了。算法上还是用求解NP问题的方法来求解,也就是N-Queens中介绍的在循环中调用递归函数求解子问题。思路是每次一次选取一个结点为根,然后递归求解左右子树的所有结果,最后根据左右子树的返回的所有子树,依次选取然后接上(每个左边的子树跟所有右边的子树匹配,而每个右边的子树也要跟所有的左边子树匹配,总共有左右子树数量的乘积种情况),构造好之后作为当前树的结果返回。代码如下: 

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector<TreeNode *> gen95(int left, int right)    {        vector<TreeNode *> ans;        if (left > right)        {            ans.push_back(NULL); // 如果不满足了,就返回空树(空节点)            return ans;        }        for (int i = left; i <= right; ++i)        {            vector<TreeNode *> lf = gen95(left, i - 1);            vector<TreeNode *> ri = gen95(i + 1, right);            for (int j = 0; j < lf.size(); ++j)                for (int k = 0; k < ri.size(); ++k)                {                    TreeNode *tmp = new TreeNode(i);                    tmp -> left = lf[j];                    tmp -> right = ri[k];                    ans.push_back(tmp);                }        }        return ans;    }
vector
<TreeNode *> generateTrees(int n) { return gen95(1, n); }};

 

leetcode Unique Binary Search Trees II