c++ - 二叉树，其中每个节点的值保存子节点的总和

这个问题是在采访中问我的。我们如何转换BT，使其中的每个节点的值都等于其子节点的总和？

最佳答案

以下是可以为您提供帮助的解决方案:(该链接以树形图说明)

Convert an arbitrary Binary Tree to a tree that holds Children Sum Property

/* This function changes a tree to to hold children sum
   property */
void convertTree(struct node* node)
{
  int left_data = 0,  right_data = 0, diff;

  /* If tree is empty or it's a leaf node then
     return true */
  if(node == NULL ||
     (node->left == NULL && node->right == NULL))
    return;
  else
  {
    /* convert left and right subtrees  */
    convertTree(node->left);
    convertTree(node->right);

    /* If left child is not present ten 0 is used
       as data of left child */
    if(node->left != NULL)
      left_data = node->left->data;

    /* If right child is not present ten 0 is used
      as data of right child */
    if(node->right != NULL)
      right_data = node->right->data;

    /* get the diff of node's data and children sum */
    diff = left_data + right_data - node->data;

    /* If node's data is smaller then increment node's data
       by diff */
    if(diff > 0)
       node->data = node->data + diff;

    /* THIS IS TRICKY --> If node's data is greater then increment left
      subtree  by diff */
    if(diff < 0)
      increment(node->left, -diff);
  }
}

请参阅link以查看完整的解决方案和说明!

关于c++ - 二叉树，其中每个节点的值保存子节点的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/5370283/