小旭讲解 LeetCode 95. 不同的二叉搜索树 II
文章目录

  • 原题
  • 思路
  • 参考

原题

给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例:

输入:3 输出: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ] 解释: 以上的输出对应以下 5 种不同结构的二叉搜索树:     1         3     3      2      1            /     /      /             3     2     1      1   3      2     /     /                            2     1         2                 3  

提示:

  • 0 <= n <= 8

思路

可以发现我们的任务是,在给定区间中找出所有不同的二叉搜索树。那么,我们可以定义一个递归函数来做这样的一件事情。同时,利用减治(分治)的思想,将大规模的问题划分成若干个小问题,进而求解即可。最后,明确下参数和返回值。

  • 参数:规定左右边界的l,r
  • 返回值:返回这个区间内,能够组成的不同二叉搜索树的根节点vector<TreeNode*> ans

为了避免重复计算,这里我们使用记忆化递归(Memoization Recursion)。

正确的代码

/**  * 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:     unordered_map<int, unordered_map<int, vector<TreeNode*>>> memo;     vector<TreeNode*> helper(int l, int r) {         if (l > r) return {nullptr};         vector<TreeNode*> ans;         if (memo.find(l) != memo.end() && memo[l].find(r) != memo[l].end()) return memo[l][r];         for (int i = l; i <= r; ++i) {             auto lnodes = helper(l, i - 1);             auto rnodes = helper(i + 1, r);             for (auto ln : lnodes) {                 for (auto rn : rnodes) {                     TreeNode* node = new TreeNode(i);                     node->left = ln, node->right = rn;                     ans.push_back(node);                 }             }         }         memo[l][r] = ans;         return ans;     };     vector<TreeNode*> generateTrees(int _n) {         return _n > 0 ? helper(1, _n) : vector<TreeNode*>{};     } };

做题时错误的思路

其实,在做题时会容易进入到一个错误的思路 —— 利用先序遍历来做。即在以递归先序遍历的方式构造这个二叉搜索树的同时,我们保留下还有多少个节点没有被使用,当所有节点都被使用完时即找到了一种可行解。

但是,上面的思路仍然是错误的。因为在先序遍历搜索时,由于回溯的特性,导致忽略了很多的可行的结果。

错误的代码

class Solution { public:     int n;     vector<TreeNode*> ans;     TreeNode* root;     TreeNode* copytree(TreeNode* node) {         if (node == nullptr || node->val == -1) return nullptr;         TreeNode *rnode = new TreeNode(node->val);         rnode->left = copytree(node->left);         rnode->right = copytree(node->right);         return rnode;     }     void helper(TreeNode* node, int l, int r, int left) {         if (l > r) return;         for (int i = l; i <= r; ++i) {             node->val = i;             --left;             if (left == 0) {                 auto rroot = copytree(root);                 ans.push_back(rroot);             }             TreeNode *lnode = new TreeNode(-1), *rnode = new TreeNode(-1);             node->left = lnode, node->right = rnode;                 helper(lnode, l, i - 1, left);             helper(rnode, i + 1, r, left - ((i - 1) - l + 1));             ++left;         }     };     vector<TreeNode*> generateTrees(int _n) {         n = _n;         root = new TreeNode(-1);         helper(root, 1, n, n);         return ans;     } };

复杂度分析

参见 LeetCode官方题解

参考

[1]. LeetCode. https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/
[2]. 维基百科. https://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0

小旭讲解 LeetCode 95. 不同的二叉搜索树 IIleetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小旭讲解 LeetCode 95. 不同的二叉搜索树 IIleetcode刷题题解