Maximum Binary Tree Radius Sum - 最大二叉树半径和

问题

一个二叉树共有个节点，范围为，每个节点拥有一个权值，所有节点的权值之和不超过。从任意节点都可以到达另一节点，且路线是唯一的，每一条的距离为1（节点与自己的距离为0，与其父节点、左右孩子节点的距离为1）。设节点权值为，所有到节点的距离小于等于的节点权值之和为 。称该权值之和为节点在半径上的半径和。下图演示了节点覆盖到的半径为的区域：

MaxBinaryTreeRadiusSum1.png

求二叉树的最大半径和。

解法

根据上图我们可以看出，找出节点半径内的所有节点并求和，即可得到该节点的半径和。二叉树中沿着父节点向上移动，和沿着左右孩子向下移动的操作不一样，因此将其区分。设表示节点在半径为的范围内，只沿着父节点向上移动的半径和，则有状态转移方程：

初始化，向上半径为时节点的半径和为，即；

节点在半径上向上的半径和，显然等于它的父结点在半径为上的半径和与它自己的权值之和，即；

下图演示节点向上半径为所覆盖到的节点：

MaxBinaryTreeRadiusSum2.png

设表示节点在半径的范围内，只沿着左右孩子节点向下移动的半径和，则有状态转移方程：

初始化，向下半径为时节点的半径和为，即；

节点在半径上向下的半径和，显然等于它的左右孩子节点在半径为上的半径和与它自己的权值之和，即；

下图演示节点向下半径为所覆盖到的节点：

MaxBinaryTreeRadiusSum3.png

还漏掉了节点的叔叔节点，下图演示节点在半径上覆盖到的所有节点，其中没有被和覆盖到的节点用绿色标记：

MaxBinaryTreeRadiusSum4.png

设为节点在半径上的半径和（本问题所求），则有状态转移方程：

初始化，半径为时节点的半径和为，即；

节点在半径上的半径和，显然等于它的父节点、左右孩子节点在半径为上的半径和，以及叔叔节点在半径为上的半径和，与它自己的权值之和，即；

遍历二叉树上所有节点，找出最大的半径和即可。该算法的时间复杂度为。

Cow Travelling

源码

MaximumBinaryTreeRadiusSum.h

MaximumBinaryTreeRadiusSum.cpp

测试

MaximumBinaryTreeRadiusSumTest.cpp