0095. Unique Binary Search Trees II =================================== 题目信息 -------- :题号: 0095. 不同的二叉搜索树 II :难度: Medium :主题: 二叉搜索树、分治、记忆化、Catalan 结构 :原题: `LeetCode 0095 `_ :重点: 从枚举根节点拆分值域,推导到缓存重复区间并组合左右子树 题目重述 -------- 给定整数 ``n``,返回所有由数值 ``1..n`` 各使用一次构成、结构互不相同的二叉搜索树。 每棵树都必须满足:任意节点左子树中的值严格小于该节点,右子树中的值严格大于该节点。答案顺序不限。 约束为 ``1 <= n <= 8``。 自建示例 -------- .. code-block:: text 输入:n = 2 输出(层序表示):[[1,null,2],[2,1]] 以 1 为根时,2 只能位于右子树;以 2 为根时,1 只能位于左子树。 .. code-block:: text 输入:n = 3 输出数量:5 以 1、2、3 为根时分别产生 2、1、2 棵树,总数为 5。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: std::vector>> memo; std::vector> computed; std::vector empty_range{nullptr}; TreeNode* cloneTree(TreeNode* node) { if (!node) { return nullptr; } return new TreeNode( node->val, cloneTree(node->left), cloneTree(node->right)); } void destroyTree(TreeNode* node) { if (!node) { return; } destroyTree(node->left); destroyTree(node->right); delete node; } std::vector directGenerate(int start, int end) { if (start > end) { return {nullptr}; } std::vector result; for (int root_value = start; root_value <= end; ++root_value) { auto left_trees = directGenerate(start, root_value - 1); auto right_trees = directGenerate(root_value + 1, end); for (TreeNode* left_tree : left_trees) { for (TreeNode* right_tree : right_trees) { result.push_back(new TreeNode( root_value, cloneTree(left_tree), cloneTree(right_tree))); } } for (TreeNode* tree : left_trees) { destroyTree(tree); } for (TreeNode* tree : right_trees) { destroyTree(tree); } } return result; } const std::vector& generateRange(int start, int end) { if (start > end) { return empty_range; } if (computed[start][end]) { return memo[start][end]; } computed[start][end] = true; auto& result = memo[start][end]; for (int root_value = start; root_value <= end; ++root_value) { const auto& left_trees = generateRange(start, root_value - 1); const auto& right_trees = generateRange(root_value + 1, end); for (TreeNode* left_tree : left_trees) { for (TreeNode* right_tree : right_trees) { result.push_back(new TreeNode( root_value, cloneTree(left_tree), cloneTree(right_tree))); } } } return result; } std::vector memoizedGenerate(int n) { memo.assign( n + 2, std::vector>(n + 2)); computed.assign(n + 2, std::vector(n + 2)); generateRange(1, n); std::vector result = std::move(memo[1][n]); for (int start = 1; start <= n; ++start) { for (int end = start; end <= n; ++end) { for (TreeNode* tree : memo[start][end]) { destroyTree(tree); } } } return result; } public: std::vector generateTrees(int n) { return memoizedGenerate(n); } }; 题解 ---- 排列建树 ~~~~~~~~ 最直接的思路是枚举 ``1..n`` 的所有插入顺序,再依次插入二叉搜索树并去除重复结构。 该方法至少检查 ``n!`` 个排列,而且不同插入顺序可能得到同一棵树。它把大量时间花在重复结构上,没有利用连续值域对根节点的约束。 根节点拆分 ~~~~~~~~~~ 考虑一个必须使用连续值域 ``[start, end]`` 的子问题。选择 ``root_value`` 作为根后,二叉搜索树性质立即确定两侧值域: .. code-block:: text 左子树使用 [start, root_value - 1] 右子树使用 [root_value + 1, end] 左右值域互不重叠。任取一棵合法左树和一棵合法右树,都能与当前根组成合法结果,因此固定根的答案是两个子树集合的笛卡尔积。 空区间 ~~~~~~ 当 ``start > end`` 时,应返回包含一个 ``nullptr`` 的集合,而不是空集合。 ``nullptr`` 表示“这一侧没有子树”,是组合过程中的一个合法选择。若返回空集合,叶节点的左右结果数都为零,笛卡尔积将无法生成任何叶节点。 .. code-block:: text 空左树集合 = {nullptr} 空右树集合 = {nullptr} 组合结果数 = 1 * 1 = 1 区间分治 ~~~~~~~~ 直接分治为每个根递归生成左右区间,再枚举所有左右组合。不同根值产生不同根节点;根值相同时,不同的左树或右树组合又产生不同结构,因此结果不会重复。 任意合法 BST 都有唯一根值。该根强制划分左右值域,递归又会生成其唯一的左右结构,所以所有合法树都会被覆盖。 重复区间 ~~~~~~~~ 直接分治会反复生成相同区间。例如生成 ``[1,4]`` 时,区间 ``[1,2]`` 可能从多个上层根选择再次出现。 记忆化以 ``(start, end)`` 为状态,第一次生成后保存该区间的全部树模板。后续访问同一区间直接复用模板集合,不再重复展开根节点与子区间。 独立节点 ~~~~~~~~ 同一棵子树模板可能与多个另一侧模板组合。若直接把模板指针挂到多个根节点下,不同返回树会共享可变节点,修改或释放其中一棵树可能影响其他树。 实现把缓存结果视为结构模板,每次组合时深复制左右子树: .. code-block:: text new root(root_value, clone(left_template), clone(right_template)) 因此每棵生成树拥有独立节点集合。顶层缓存的所有权最终转移给返回结果,其余区间模板在返回前释放。 根值分组 ~~~~~~~~ ``n = 3`` 时,各根节点的组合数量如下: .. list-table:: :header-rows: 1 * - 根值 - 左区间树数 - 右区间树数 - 组合数 * - 1 - 1 个空树 - 2 - 2 * - 2 - 1 - 1 - 1 * - 3 - 2 - 1 个空树 - 2 固定根的数量是左右结果数之积,对所有根求和正是 Catalan 递推结构。 复杂度 ~~~~~~ 设第 ``n`` 个 Catalan 数为 ``C_n``,它也是最终树的数量。每棵返回树包含 ``n`` 个节点,仅构造独立输出就需要 ``Theta(n * C_n)`` 时间与返回空间。 记忆化还保存较短区间的树模板,其节点总量仍为 ``O(n * C_n)``;递归深度为 ``O(n)``。直接分治会额外重复生成相同区间,实际工作量更高。