二叉树的深度优先搜索应用实例—员工派对

公司要举办一个员工派对,公司里所有的员工都有资格来参加。如图 1 所示,该公司的组织结构是一个二叉树结构。如果一个节点 A 有双亲节点 B,则代表 B 是 A 的上司。
公司的组织结构(1)
图1:公司的组织结构(1)

实际上,每一个员工为派对所能带来的贡献不一样,有的人幽默,就能使派对更加有趣,而有的人恰恰相反。树上每一个节点圆圈里的数字便代表每一个员工为派对所能带来的贡献值。然而,假如该公司里的所有员工都对自己的上司不满意(如果其有上司的话),那么如果一个员工来到派对,其上司就不能来到派对,反之亦然。

但员工和员工上司的上司是可以一起参加派对的,因为他们互相不熟悉。如果你是董事长的秘书,并且已知公司组织结构,应该怎么邀请员工,使得任何一组员工和上司不会同时出现在派对中,并且使得邀请的所有员工的贡献值之和最大?

如图 2 所示,秘书必然会邀请标为灰色的两个员工来参加派对,其派对贡献值之和为 4+5=9。在这一节中,我们需要找到最优的邀请员工方法。
应被邀请的员工
图 2:应被邀请的员工

再来看一个例子,如果公司的组织结构如图 3 所示,那么为了达到最优贡献值,秘书会邀请被标为灰色的三位员工,其贡献值之和为 1+3+3=7。
公司的组织结构(2)
图 3:公司的组织结构(2)

首先,我们分析一下前提条件。前面的题目说到任何一组员工和上司均不能同时出现在派对中,所以员工和员工之间的关系是题目的关键。如图 4 所示,我们可以把二叉树分层来分析公司员工和员工之间的关系。
二叉树分层
图 4:二叉树分层

按题目所说,如果邀请了所有第四层员工来到派对,则第五层的所有员工都不能出现在派对中,而可以邀请到部分第三层的员工。在邀请员工时需要统观全局寻求最优,因为对每一层的邀请的决定都影响相邻的层的邀请。如图 5 所示,这里列举了一些不同的邀请方案。
员工邀请方案
图 5:员工邀请方案

所以对于每一个节点(员工)而言,秘书都要做一个选择:邀请还是不邀请。在这种情况下,就需要对比邀请能得到的贡献值和不邀请能得到的贡献值。

因此我们不妨为每一个节点(员工)设两个值:如果邀请能得到的贡献值和不邀请能得到的贡献值。如图 6 所示,例子中的每一个节点(员工)旁边都有邀请和不邀请两个值。
二叉树最底层更新
图 6:二叉树最底层更新

我们从最底层开始更新,因为最底层的员工只会影响到其上一层(上司)的到场。在图 6 中可以看到节点 4、节点 5 和节点 6 的邀请值和不邀请值分别为其本身的贡献值和 0。这层逻辑很简单:如果邀请,则得到相对应的贡献值;如果不邀请,则得到 0 贡献值。

这时我们使用最底层的邀请值和不邀请值来更新上一层。如图 7 所示。
二叉树第二层更新
图 7:二叉树第二层更新

先分析节点 2,如果邀请了节点 2 的员工,则会得到 4 点贡献值,但就不能再邀请在节点 4 和节点 5 的员工;如果不邀请节点 2 的员工,就可以邀请节点 4 和节点 5 的员工,仍得到 4 点贡献值。再分析节点 3,如果邀请节点 3 的员工,则可以得到 5 点贡献值;如果不邀请节点 3 的员工,则可以邀请节点 6 的员工,可得到 1 点贡献值。

如图 8 所示,最后就可以更新根节点 1 的值,值得注意的是,更新二叉树的时候趋向于自下而上,自叶子节点向根节点,因为二叉树的根节点始终为一,所以应该最后更新从而得到唯一答案。如果邀请节点 1 员工,则会得到节点 1 的 3 点贡献值,节点 4 和节点 5 的共 4 点贡献值,以及节点 6 的 1 点贡献值;如果不邀请,则可以得到节点 2 的 4 点贡献值和节点 3 的 5 点贡献值。
二叉树第三层更新
图 8:二叉树第三层更新

相互权衡之后,秘书只有两种可以采取的方案,如图 9、图 10 标灰的节点所示。
可供选择的方案一
图 9:可供选择的方案一

可供选择的方案二
图 10:可供选择的方案二

在以上的分析中,我们可以通过观察每个节点的邀请值和不邀请值总结出以下结论。
  1. 每一个节点的邀请值=该节点的贡献值+左子节点的不邀请值+右节点的不邀请值。
  2. 每一个节点的不邀请值=左子节点邀请值和不邀请值中的较大值+右子节点邀请值和不邀请值中的较大值。

而这两个结论也不难被推理出。对于结论 1 来说,如果一个节点的员工被邀请,则其所有的子节点都不能被邀请,即要加上两个子节点的不邀请值。对于结论 2 来说,如果一个节点的员工没有被邀请,则其子节点的员工既可被邀请也可以不被邀请,从而取二者中的最大值以求出最优解。

如果节点的定义为:
#类的定义
class treenode:                 #二叉树节点的定义
    def __init__(self, val):
    def __init__(self, val):
    self.val = val             #该节点的贡献值
    self.left = None            #左侧子节点
    self.right = None            #右侧子节点

那么任何一个节点(用 node 表示)的邀请值(Attend_Value)与不邀请值(Absent_Value)则是:
#邀请值和不邀请值的计算
Attend_Value = node.val + node.left.Absent_Value + node.right.Absent_Value
Absent_Value = max(node.left.Attend_Value, node.left.Absent_Value)+
max(node.right.Attend_Value, node.right.Absent_Value)

因此现在需要解决的问题是:如何得到子节点的邀请值与不邀请值,也就是说,如何得到 root.left.Attend_Value、root.left.Absent_Value、root.right.Attend_Value与root.right.Absent_Value。

答案很简单,也是深度优先搜索的核心思想,向最“深”处递归。顺次找到子节点的子节点的邀请值与不邀请值,向树的叶子节点递归,找到 root.left.left.Attend_Value、root.left.left.Absent_Value、root.left.right.Attend_Value、root.left.right.Absent_Value、root.right.left.Absent_Value、…,直到找到叶子节点已经赋初值后的邀请值和不邀请值,即利用递归来深度优先遍历二叉树。

现在我们尝试把之前的思路用 Python 实现出来。整个问题的代码可以大致分为输入、建树、DFS、输出几大部分。回到原题,原题的输入形式为按树节点的编号从小到大输入该节点的派对贡献值,如果有的节点空缺则输入 null,如图 11 所示。
输入二叉树示例
图 11:输入二叉树示例

则输入样例应为:

3 4 5 1 3 null 1


所以我们只需用列表将整棵树读入,然后经过 treenode 类处理之后,将读入的 value 赋值到 treenode 类的 val 中。而建树,则可以用到前文曾讲解过的二叉树的性质,任何一个有子节点的节点,其左子节点的标号等于该节点标号的二倍,右子节点的标号等于该节点标号的二倍加一。通过这个规律,我们可以通过标号来寻找自己的左子节点和右子节点从而完成建树。

以下两段代码为建树:
#Input为存放输入的列表
for item in Input:  #循环将所有输入转换为treenode类
    tmp = treenode(item)
    tree.append(tmp)

通过二叉树的性质确定每个节点的子节点:
for item in tree:     #循环,在此之前cnt赋初值为1,tree是一个存有treenode类的列表
    if item.val == "null":
        continue
    if 2 * cnt <= len(Input) and tree[2 * cnt - 1].val != "null":  #判断是否有左子节点
        item.left = tree[2 * cnt - 1]
    if 2 * cnt + 1 <= len(Input) and tree[2 * cnt].val != "null":  #判断是否有右子节点
        item.right = tree[2 * cnt]
    cnt += 1

以下便是深度优先搜索函数 DFS() 和输出函数 ans():
def ans(root):
    at_val, ab_val = DFS(root) #at_val和ab_val分别存储root节点的邀请值和不邀请值
    return max(at_val, ab_val) #返回两个值中的最大值,此值为派对所能得到的最大贡献值
    def DFS(node):      #参数为root节点,DFS方法通过递归返回root节点的邀请值和不邀请值
    if(node == None):   #如果不存在现有的参数节点,返回邀请值和不邀请值为0,0
        return 0, 0
    left_at, left_ab = DFS(node.left)      # 存储参数节点左子节点的邀请值和不邀请值
    right_at, right_ab = DFS(node.right)     # 存储参数节点右子节点的邀请值和不邀请值
    Attend_Value = int(node.val) + left_ab + right_ab # 求出参数节点的邀请值
    Absent_Value = max(left_at, left_ab)+ max(right_at, right_ab)      #求出参数节点的不邀请值
    return Attend_Value, Absent_Value      #返回参数节点的邀请值和不邀请值