最优字母二叉树问题（Huffman树扩展版本） 题目描述 给定一个包含n个字符的集合，每个字符有一个出现频率f[ i ]。现在需要构建一棵二叉树，每个字符作为叶子节点，树的带权路径长度定义为每个字符的深度乘以频率的总和。与标准Huffman树不同，这里要求二叉树必须满足搜索树的性质（即对于每个节点，左子树的所有字符都小于当前节点字符，右子树的所有字符都大于当前节点字符）。求满足搜索树性质的最小带权路径长度。 解题过程 问题分析 标准Huffman树只考虑频率，不考虑字符顺序 本题要求二叉树同时满足搜索树性质，意味着字符必须按顺序排列 需要选择根节点，将字符集划分成左右子树 关键观察 将字符按值从小到大排序：c₁ < c₂ < ... < cₙ 频率数组f对应排序后的字符 对于区间[ i,j ]，选择根节点k(i ≤ k ≤ j) 左子树包含[ i,k-1]，右子树包含[ k+1,j ] 状态定义 定义dp[ i][ j]表示字符区间[ i,j ]构成的最优二叉搜索树的最小带权路径长度 预处理前缀和数组sum，其中sum[ i][ j] = f[ i] + f[ i+1] + ... + f[ j ] 状态转移方程 当区间长度为1时：dp[ i][ i] = f[ i ] 当区间长度大于1时： dp[ i][ j] = min(dp[ i][ k-1] + dp[ k+1][ j] + sum[ i][ j]) 对于所有k ∈ [ i,j ] 解释：选择k为根时，左右子树的带权路径长度加上所有节点的频率（因为根节点深度为0，每个节点深度增加1） 算法步骤 排序字符并对应调整频率数组 计算前缀和数组 按区间长度从小到大计算dp值 最终结果存储在dp[ 0][ n-1 ]中 复杂度分析 时间复杂度：O(n³)（三重循环） 空间复杂度：O(n²) 示例演示 假设字符集[ a,b,c]，频率[ 1,2,3 ]： 排序后字符顺序不变 计算dp[ 0][ 2 ]：分别尝试以a、b、c为根 最终得到最小带权路径长度 这种算法保证了二叉树既满足搜索树性质，又具有最小的带权路径长度，是Huffman树在有序字符集上的扩展应用。