问题
拥有n个节点的二叉树,节点范围为[1,n],节点i的权值为正整数vi,整个二叉树的权值为所有节点的权值之和。现在要求只保留m个节点(0<m<n−1),剪裁掉的节点数量为n−1−m,要求剩余部分仍然是一个二叉树,而不能是多个二叉树。如图:
正确剪裁
错误剪裁
对于拥有n个节点的二叉树,求出保留m个节点的二叉树的最大权值。
解法
设f(i,j)表示以节点i为根节点的树上,保留j个节点(包括节点i自己)的最大权值。因此有转移方程如:
f(i,j)={vimax{f(lefti,k)+f(righti,j−1−k)+vi}(initialize)(loop)i∈[1,n],j=1i∈[1,n],j∈[2,n] (1) 节点数量为1的二叉树,其最大权值即为节点自己的权值,因此f(i,1)=vi;
(2) 对于根节点为i的二叉树,只留j个节点。当左子树上有k个节点(1≤k≤j−1),则右子树上有j−1−k个节点,因为左右子树的节点数量之和为j−1(根节点i占一个节点)。设其左右孩子节点为lefti和righti,左子树的最大权值为f(lefti,k),右子树的最大权值为f(righti,j−1−k),根节点的子树的最大权值为f(i)=f(lefti,k)+f(righti,j−1−k)+vi。遍历k∈[1,j−1],在所有可能中选取使f(i,j)最大的即可;
f(n,m)即为该二叉树留下m个节点时的最大权值。该算法的时间复杂度是O(n×m)。
源码
MaximumBinaryTree.h
MaximumBinaryTree.cpp
测试
MaximumBinaryTreeTest.cpp