二叉树的深度优先搜索应用实例—城市危机

已知某个国家中的城市呈二叉树形状分布。这时国家突然出现了断电危机。现在政府要求电力修理部队可以从任意一个城市出发来修理各个城市的电力设施。每个城市有不同的紧急程度,所以以不同的路径来修理电力设施会得到不同的收益。

如图 1 所示,二叉树节点上的数字代表修理电力设施的收益(可以为负)。不幸的是,修理部队因为种种原因不能掉头,这就意味着其不能来到同一个城市两次,城市与城市之间的边也只能走一回。在这种情况下,我们需求解出一条路径,使修理的收益最大,路径上的和最大。
例子(1)
图 1:例子(1)

如果城市的紧急程度如图 1 所示,那么最优的修理线路应该是灰色的路径,总共的收益为 7。

而如果城市的紧急程度如图 2 所示,那么在这个特定的例子中,最优路线为灰色的路径,且不经过根节点,总共的收益为24。

例子(2)
图 2:例子(2)

而图 3 所示的这个例子中,最佳路线只为一个顶点,总共收益为 6。
例子(3)
图 3:例子(3)

在分析题目的同时,我们会找到该题目最重要的约束条件,即访问过的节点不能再次访问。这也间接地暗示着,如果修理部队到达了一个在叶子节点上的城市,就无法再去其他城市了。当然修理部队不一定只在叶子节点终止路径,其可以在任何时候停止,及时止损。

仍然依照前面的思路,尽量地简化问题。对于这个问题而言,树上的每一个节点(城市)都只有两个可能:继续或者停止。继续修理的前提条件为路径的两段至少有一段不为叶子节点,而停止路径则没有条件约束。我们依旧将二叉树分层,按层数来实现更新,最后通过根节点来得出最终答案。这也是深度优先搜索在二叉树中的核心思想。

让我们来看一个例子。每一个节点都有两个值:停或不停。“停”值可以被理解为:以当前节点为根节点的子树中,所有已经结束的路径中所能得到收益的最大值;而“不停”值可以被理解为:以当前节点为根节点的子树中,仍可被延伸的所有路径中所能得到收益的最大值。

如图 4 所示,二叉树的底层节点 4、节点 5、节点 6、节点 7 已被更新,其节点的停与不停值都是一样的,为自身的收益值。因为在每一个只有一个节点的子树中,能否被延伸所对应的情况是相通的。
底层节点
图 4:底层节点

这时我们再来更新上一层的节点,先分析节点 2 的停值和不停值。如图 5 所示,节点 2 可能的停值有三种,因为在以节点 2 为根节点的子树中,所有可能已经停止的路径有三种,如图 5 所示。
停止的三种路径
图 5:停止的三种路径

图 5(a)和图 5(b)均为只有一个叶子节点已停止的路径,收益为节点数值本身。而图 5(c)是一个经过节点 2 的路径。这条路径的两段都是叶子节点,所以已经停止了,其收益为 10+2+12=24。

因此节点 2 的停值有三个候选收益值:10,12,24。这时我们只需要记录最大值,因为其他的值已经不可能成为题目的最优解。节点 2 的停值可以被更新为 24。

再来分析节点 2 的不停值。如图 6 所示,可延伸的路径也有三种:经过节点 2 与节点 4、经过节点 2 与节点 5、经过节点 2。
可延伸的三种路径
图 6:可延伸的三种路径

这三种路径均可以向节点 1 方向继续延伸,所以并没有停止。因此,不停有三个可能值:12,14,2。我们也如同停值一样,只记录最大值,因此节点 2 的不停值为 14。

最终我们确认了节点 2 的停值和不停值分别为 24 和 14,如图 7 所示。这时我们再来用同样的思路分析节点 3。
节点2的情况
图 7:节点 2 的情况

依旧先来分析节点3的停值。如图 8 所示,停止的路径有这三种情况:在节点 6 停止、在节点 7 停止、经过节点 6 与节点 3 后在节点 7 停止。因此,节点 3 的停值有两个可能值:2 和 1。因此我们取最大值 2 记录为节点 3 的停值。
节点3停止的三种路径
图 8:节点 3 停止的三种路径

继而分析节点 3 的不停值。如图 9 所示,节点 3 的可延伸路径也只有三种情况:经过节点 3、经过节点 3 与节点 6、经过节点 3 与节点 7。因此,节点 3 不停有三个可能值:-2,0,-1。我们取最大值 0 作为其不停值。
节点3可延伸的三种路径
图 9:节点3可延伸的三种路径
节点3可延伸的三种路径(续)
图 9:节点 3 可延伸的三种路径(续)

我们更新不停值的意义,其实就是为了更新更高层的停值。因为我们现在通过刚才的分析大致可以总结出来:节点 k 的停值=max(其左子节点的不停值,其右子节点的不停值,其左子节点的停值,其右子节点的停值,其左子节点的不停值加上其右子节点的不停值再加上k自身的收益值)。

一个节点的停值需分析比较五个值,但因为叶子节点的停值与不停值相同,所以我们只分析比较了三种情况。这个规律会在我们更新节点 1 的停值时更明显地呈现出来。

最后,到达根节点。根节点的可延续的路径有三种可能(但两个值重复),不延续的路径有五种可能。图 10 所示为根节点更新前的情况。
更新根节点前的情况
图 10:更新根节点前的情况

依旧按照之前的思路。首先,节点 1 的不停值。如图 11 所示,可延伸路线有三种情况:节点 1 加上左子节点的不停路径、节点1加上右子节点的不停路径、节点 1。因此,不停有两个可能值:1,15。到此,我们也可以总结出节点 k 的不停值=max(节点 k 自身的收益值,k 自身的收益值再加上其左子节点的不停值,k 自身的收益值再加上其右子节点的不停值)。
根节点的三种可延伸路径
图 11:根节点的三种可延伸路径
 
其中的逻辑不复杂,如果要求路径不能停止,要不从左子树或右子树中挑一个子树中不停的路径连接上现节点 k,要不就不连接子树保留的路径而从节点 k 重新开启新的路径。

再来分析节点 1 的停值。如图 12 所示,正如上述内容所说,不延伸路径会有五种情况:左子节点的停止路径、右子节点的停止路径、左子节点的可延伸路径、右子节点的可延伸路径、根节点加上两个子节点的可延伸路径。因此,节点 1 的停值有五个可能值:24,2,14,0,15。图 12~图 16所示是与五种情况一一对应的示意图。
左子节点的停止路径
图 12:左子节点的停止路径

右子节点的停止路径
图 13:右子节点的停止路径

左子节点的可延伸路径
图 14:左子节点的可延伸路径

右子节点的可延伸路径
图 15:右子节点的可延伸路径

根节点加上两个子节点的可延伸路径
图 16:根节点加上两个子节点的可延伸路径

节点的停值中的逻辑也不难,值得注意的是,五种情况的前两种左子节点的停值、右子节点的停值分别为左子树和右子树中停止路径的最大值,有可能成为全图路径的最大值。而中间两种情况左子节点的不停值、右子节点的不停值记录的分别为左子树和右子树的可延伸路径的最大值。

虽然这些路径还可继续,但也可以随时终止,即时止损(因为收益值可以为负)。最后一种情况则是将左子树和右子树的可延伸路径串联起来,如果所有节点的收益值为正,则其必为全图路径的最大值。

遍历完所有的节点,我们输出根节点不停值与停值中的较大值作为答案,在图 17 所示的二叉树中最大值为 24,相对应的路线是节点 4、节点 2、节点 5。
输出最大值

图 17:输出最大值

我们通过深度优先算法遍历了所有的节点,深度优先算法的思想是首先遍历最底层的节点,然后逐步上移到根节点。

每遍历一个节点,输出两个值以便之后的节点作决定,一个是停值,一个是不停值。我们现在的工作是找到一个适用于所有节点的停值与不停值的输出方法。

来看以下代码:
#深度优先
class TreeNode:              #二叉树节点定义
    def __init__(self, x):
    self.val = x             #节点值
    self.left = None           #左子节点
    self.right = None          #右子节点
def helper(self, root):         #helper方法,输出一个二维数组 [不停值,停值]
    leftY, leftN = self.helper(root.left) #得到root左子节点的不停值与停值
    rightY, rightN = self.helper(root.right) #得到root右子节点的不停值与停值
    yes = max(root.val + leftY, root.val + rightY, root.val)  #不停值(yes代表继续)
    no = max(leftN, rightN, leftY, rightY, root.val + leftY + rightY) #停值
    return yes, no            #输出 root节点的[不停值,停值]

root 节点的不停值是以下三个值中的最大值:root 值、root 值+左子节点的不停值、root 值+右子节点的不停值。root 节点的停值是以下五个值中的最大值:左子节点的不停值、右子节点的不停值、左子节点的停值、右子节点的停值、root 值+左右子节点的不停值。

到现在为止,我们还没有考虑空节点的情况。如果节点为空,我们应该输出两个最小值,让 max() 方法过滤掉这个空节点。完整代码如下所示。
#城市危机最终代码
class Solution:
    def maxPathSum(self, root):     #输出最大路径和的方法
        return max(self.helper(root))  #调用helper方法,传入根节点,输出返回的两个值中的最大值
    def helper(self, root):       #helper方法,输出一个二维数组 [不停值,停值]
        if root == None:               #如果节点为空,输出两个最小值
            return float('-int'), float('-int')
        leftY, leftN = self.helper(root.left)     #得到左子节点的不停值与停值
        rightY, rightN = self.helper(root.right)   #得到右子节点的不停值与停值
        yes = max(root.val + leftY, root.val + rightY, root.val)      #不停值
        no = max(leftN, rightN, leftY, rightY, root.val + leftY + rightY)  #停值
        return yes,no                #输出 [不停值,停值]