汇总子值并保存在中间步骤中计算的值

Question

struct node { 
    int value; 
    struct node* left; 
    struct node* right; 
    int left_sum;
    int right_sum;
} 

在二叉树中,从特定节点,有一个简单的递归算法来汇总其所有子值.有没有办法保存在中间步骤计算的值,并将其存储为left_sum和right_sum在子节点？

通过添加struct node* parent节点定义的链接,自下而上更容易吗？

Answer 1

不,这显然是一种递归练习.想想总和意味着什么.它是零加上"从根向下的所有值的总和".

有趣的是,"从根向下的所有值的总和"是根节点的值加上 "从其左侧节点向下的所有值的总和" 加上 "从其右侧节点向下的所有值的总和".

希望你能看到我要去的地方.

递归的本质是根据具有终止条件的类似,更简单的操作来定义操作.

在这种情况下,终止条件是树的叶节点,或者为了使代码更简单,超出叶节点.

检查以下伪代码:

def sumAllNodes (node):
    if node == NULL:
        return 0
    return node.value + sumAllNodes (node.left) + sumAllNodes (node.right)

fullSum = sumAllNodes (rootnode)

这就是它的全部内容.使用以下树:

           __A(9)__
          /        \
      B(3)          C(2)
     /    \             \
D(21)      E(7)          F(1)

使用伪代码,sum是A(9)的值加上左右子树的总和.

左子树A是B(3)的值加上其左右子树的总和.

左子树B是D(21)的值加上其左右子树的总和.

左子树D是NULL(0)的值.

后来,右子树A是价值C(2)加的总和其左,右子树,它的左子树是空的,它的右子树是F(1).

因为你这样做递归,你不明确永远走你的路了树.这是事实,递归调用返回的是具有该能力的求和值.换句话说,它发生在封面下.

你的问题的另一部分并不是真的有用,当然,可能有未说明的要求,我没有考虑到,因为他们是,嗯,...未说明:-)

有没有办法保存在中间步骤中计算的值,并将它们作为left_sum和right_sum存储在子节点中？

您实际上从未重复使用给定子树的总和.在求和计算,你将计算B-and-below子树只有一次,因为它增加的部分A和C-and-below子树.

您可以存储这些值,以便B包含值和两个总和(左和右) - 这意味着对树的每次更改都必须将自身传播到根,但它是可行的.

现在有在某些情况下可能有用.例如,如果树本身很少变化但是你非常想要总和,那么在更新时这样做是明智的,这样成本就会在很多读取中分摊.

我有时会将这种方法与数据库一起使用(大多数情况下读取的次数远多于写入的数据库),但在"普通"二叉树中看到它是不常见的.

另一种可能的优化:只将sum作为树对象中的单独变量.将其初始化为零,然后,无论何时添加节点,都将其值添加到总和中.

删除节点时,从总和中减去其值.这为您提供了非常快速的O(1)"返回总和"功能,而无需在更新时向上传播.

缺点是你只有一棵树的总和,但我很难想出一个有效的用例需要子树的总和.如果您有这样的用例,那么我会选择以下内容:

def updateAllNodes (node):
    if node == NULL:
        return 0
    node.leftSum = updateAllNodes (node.left)
    node.rightSum = updateAllNodes (node.right)
    return node.value + node.leftSum + node.rightSum

change the tree somehow (possibly many times)
fullSum = updateAllNodes (root)

换句话说,只需在每次更改后更新整个树(或批量更改,然后更新,如果您知道发生了相当多的更改).这可能比尝试将其作为树更新本身的一部分更简单一些.

您甚至可以使用一个单独dirtyFlag的树,每当树更改时设置为true,并在计算和存储总和时设置为false.然后在求和计算代码中使用它来仅执行重新计算(如果它是脏的)(换句话说,总和的高速缓存).

那样的代码就像:

fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)
fullSum = updateAllNodes (root)

只会在第一次调用时产生费用.由于总和被缓存,其他四个应该是快速的.