力扣 LeetCode 1569. 将子数组重新排序得到同一个二叉搜索树的方案数 - 力扣（LeetCode） 1569. 将子数组重新排序得到同一个二叉搜索树的方案数 - 给你一个数组 nums 表示 1 到 n 的一个排列。我们按照元素在 nums 中的顺序依次插入一个初始为空的二叉搜索树（BST）。请你统计将 nums 重新排序后，统计满足如下条件的方案数：重排后得到的二叉搜索树与 nums 原本数字顺序得到的二叉搜索树相同。 比方说，给你 nums = [2,1,3]，我们得到一棵 2 为根，1 为左孩子，3 为右孩子的树。数组 [2,3,1] 也能得到相同的... 思路 考虑构建二叉搜索树的过程。对于一个元素 x 和它在初始树上的任一祖先 fa ，如果 x 先于 fa 被放入，那么 x 会顶替祖先 fa 的位置。因此「生成相同的二叉搜索树」等价于「任意元素 x 不能先于其祖先加入」。 这相当于求初始二叉搜索树的拓扑序数量。假设结点 x 的子树大小为 sz_x ，拓扑序数为 f_x ，那么两个子树 x,y 合并后的拓扑序数为 f_x \times f_y \times \binom{sz_x+sz_y}{sz_x} 。模拟建树过程后做上述 DP 可以 O(n^2) 通过本题。 但本题还可以优化。展开所有的组合数公式，我们发现每个结点 x 本身贡献了 (sz_x-1)! 的阶乘（ x 本身不参与子树合并，所以少 1 ），同时除根结点外向上贡献了 \frac{1}{sz_x!} 的逆元。 因此对大小为 n 的树，其拓扑序数为 n!\times (\prod_x \frac{1}{sz_x}) ，这让我们得到了一个简单的 O(n) 计算公式。 接下来的目标是快速构建二叉搜索树。考虑二叉搜索树的性质， x 的父节点一定是最接近 x 的更小元素 l 和更大元素 r 之一。进一步地，一定是其中更晚加入的那个。 因此我们可以维护一个包含元素 1 到 n 的链表，然后倒序处理每一个元素 x ，找到 x 在链表上的前驱和后继，更新其父结点的子树大小，然后删除 x 。时间复杂度 O(n) 。 代码 class Solution { public: static constexpr int M=1000000007,N=1000; //id：加入时间 sz：子树大小 inv：逆元 l,r：链表前驱后继 int id[N+5],sz[N+5],inv[N+5],l[N+5],r[N+5]; int numOfWays(vector<int>& v) { int i,n=v.size(),res=1; //初始化阶乘，加入时间和链表 for(i=1;i<=n;i++){ id[v[i-1]]=i; sz[i]=1; res=1llresi%M; l[i]=i-1; r[i]=i+1; } id[0]=id[n+1]=0; //线性逆元 if(!inv[0]){ inv[0]=inv[1]=1; for(i=2;i<=N;i++)inv[i]=1ll(M-M/i)inv[M%i]%M; } //倒序处理 reverse(v.begin(),v.end()); for(auto i:v){ //加入的 i 为其前驱/后继中最晚出现的元素，i 未被删除，可以直接定位 int x=l[i],y=r[i]; //更新父节点的大小 sz[id[x]>id[y]?x:y]+=sz[i]; //在链表中删除 i l[y]=x; r[x]=y; //更新答案，乘上子树大小的逆元 res=1llres*inv[sz[i]]%M; } return res-1; } }; 1 个帖子 - 1 位参与者 阅读完整话题

  • 情报分类：综合情报
  • 分类依据：内容未命中明确的垂直分类规则，归入综合情报
  • 信息来源：服务器 / LINUX DO - 最新话题
  • 发布时间：2026/10/18 15:06:55