问题
一个二叉树共有n个节点,范围为[1,n],每个节点拥有一个权值,所有节点的权值之和不超过m。从任意节点i都可以到达另一节点j,且路线是唯一的,每一条的距离为1(节点与自己的距离为0,与其父节点、左右孩子节点的距离为1)。设节点i权值为vi,所有到节点i的距离小于等于radius的节点权值之和为∑p=1nivp 。称该权值之和为节点i在半径radius上的半径和。下图演示了节点4覆盖到的半径为2的区域:
求二叉树的最大半径和。
解法
根据上图我们可以看出,找出节点i半径radius内的所有节点并求和,即可得到该节点的半径和。二叉树中沿着父节点向上移动,和沿着左右孩子向下移动的操作不一样,因此将其区分。设f(i,j)表示节点i在半径为j的范围内,只沿着父节点向上移动的半径和,则有状态转移方程:
f(i,j)={0f(fatheri,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,fatheri∈[1,n],0≤j−1<j≤m (1) 初始化,向上半径为0时节点i的半径和为0,即g(i,0)=0;
(2) 节点i在半径j上向上的半径和,显然等于它的父结点fatheri在半径为j−1上的半径和与它自己的权值之和,即f(i,j)=f(fatheri,j−1)+vi;
下图演示节点7向上半径为3所覆盖到的节点:
设g(i,j)表示节点i在半径j的范围内,只沿着左右孩子节点向下移动的半径和,则有状态转移方程:
g(i,j)={0g(lefti,j−1)+g(righti,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,lefti,righti∈[1,n],0≤j−1<j≤m (1) 初始化,向下半径为0时节点i的半径和为0,即g(i,0)=0;
(2) 节点i在半径j上向下的半径和,显然等于它的左右孩子节点lefti,righti在半径为j−1上的半径和与它自己的权值之和,即g(i,j)=g(lefti,j−1)+g(righti,j−1)+vi;
下图演示节点1向下半径为3所覆盖到的节点:
还漏掉了节点i的叔叔节点unclei,下图演示节点4在半径2上覆盖到的所有节点,其中没有被f(4,2)和g(4,2)覆盖到的节点用绿色标记:
设h(i,j)为节点i在半径j上的半径和(本问题所求),则有状态转移方程:
h(i,j)={0f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vi(initialize)(loop)i∈[1,n],j=0i,fatheri,unclei,lefti,righti∈[1,n],0≤j−2<j−1<j≤m (1) 初始化,半径为0时节点i的半径和为0,即h(i,0)=0;
(2) 节点i在半径j上的半径和,显然等于它的父节点、左右孩子节点在半径为j−1上的半径和,以及叔叔节点在半径为j−2上的半径和,与它自己的权值之和,即h(i,j)=f(fatheri,j−1)+g(unclei,j−2)+g(lefti,j−1)+g(righti,j−1)+vi;
遍历二叉树上所有节点,找出最大的半径和即可。该算法的时间复杂度为O(n×m)。
Cow Travelling
源码
MaximumBinaryTreeRadiusSum.h
MaximumBinaryTreeRadiusSum.cpp
测试
MaximumBinaryTreeRadiusSumTest.cpp