小旭讲解 LeetCode 95. 不同的二叉搜索树 II
小旭讲解 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

欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-95-unique-binary-search-trees-ii/
最后修改日期:2020年7月23日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。