解决方案


方法:递归

算法

从问题的描述中,可以清楚地了解到,我们需要在给定树的每个结点处找到其坡度,并将所有的坡度相加以获得最终结果。要找出任意结点的坡度,我们需要求出该结点的左子树上所有结点和以及其右子树上全部结点和的差值。

因此,为了找出解决方案,我们使用递归函数 traverse,在任何结点调用该函数,都会返回当前结点下面(包括其自身)的结点和。借助于任何结点的左右子结点的这一和值,我们可以直接获得该结点所对应的坡度。

下面的动画描述了值的传递和坡度计算的方式:

!?!../Documents/563_Binary.json:1000,563!?!

复杂度分析

  • 时间复杂度:。其中 是结点的数目。每个结点访问一次。
  • 空间复杂度:。在最糟糕的情形下,当树倾斜时,树的深度可以达到 。平均情况下,树的深度为