二叉树划分为K个子树的最小最大高度最优算法探讨

问题明确 #

你的需求是将二叉树划分为K个子树，使得所有子树的最大高度尽可能小，其中节点距离定义如下：

D(V) = 0                    ... 若V是子树的根
     = Infinity             ... 若V是原树的根但不是子树的根
     = 1 + D(V的父节点)    ... 其他情况

注意原树的根必须作为某个子树的根，否则其距离为无穷大，直接导致最大高度无法满足最小化目标。

贪心算法的局限性 #

你提到线性链状树是贪心的反例，这点很关键。比如长度为5的链（根为1，节点1-2-3-4-5），要划分为2个子树：贪心从叶子切割会得到最大高度3，但最优解是在节点3处切割，最大高度仅为2，贪心无法保证全局最优。

高效解法：二分答案+贪心验证 #

这是这类「最小化最大值」问题的经典高效思路，时间复杂度为O(N log H)（N为节点数，H为原树高度），实际表现远优于多数动态规划实现。

核心步骤 #

1. 确定二分范围：
   • 下界low=0（当K=N时，每个节点单独成子树）
   • 上界high=原树高度（当K=1时，整棵树为一个子树）
2. 贪心验证可行性：
   给定候选高度h，递归遍历树：
   • 跟踪当前节点到所在子树根的距离，若距离超过h，则必须在其父节点处切割，将当前节点作为新子树的根（原树根不能切割）。
   • 统计所需切割次数，若切割次数+1 ≤ K（+1是原树根本身的子树），则h是可行的，尝试更小的候选值；反之则需要更大的候选值。

动态规划解法 #

确实可以用动态规划解决，但时间复杂度更高，仅适合K较小的场景。

状态定义 #

设dp[u][k]表示以u为根的子树划分为k个子树时，子树集合的最大高度的最小值。

状态转移 #

对于节点u的左子树L和右子树R，枚举左子树划分i次、右子树划分j次（i+j ≤ k-1，因为u本身占1个子树）：

dp[u][k] = min{ max( dp[L][i], dp[R][j], 1 + max( left_max_dist, right_max_dist ) ) }

其中left_max_dist是左子树划分i次后，子树根到u的最大距离（即未被切割的分支中，节点到u的距离）。

该DP的时间复杂度为O(N*K²)，当K接近N时，效率远低于二分答案法。

总结 #

• 优先选择二分答案+贪心验证，高效且实现简洁，适合大多数场景。
• 动态规划可解决问题，但仅在K较小时更有优势。

内容的提问来源于stack exchange，提问作者Liu