c++ - 在不使用额外的整数指针参数的情况下，用节点左侧所有值的总和替换树的每个节点

Question

给定一棵二叉树，我需要将每个节点中的值更改为节点左侧节点中所有值的总和。本质上，每个节点的值应该等于在树的有序遍历中早先访问到该节点的所有节点值的总和。重要的一点是这必须在不使用整数指针参数的情况下完成。我可以用整数指针参数来解决它来保存这样的总和。如果没有这个整数指针变量，当我从其父节点访问节点的右侧时，如何保持和。

void modifyBST(struct node *root, int *sum) {

    if (root == NULL)  return;

    // Recur for right subtree
    modifyBSTUtil(root->left, sum);

    // Now *sum has sum of nodes in right subtree, add
    // root->data to sum and update root->data
    *sum = *sum + root->data;
    root->data = *sum;

    // Recur for left subtree
    modifyBSTUtil(root->right, sum);
}

如何修改此方法以便删除 int *sum。 我的完整程序在这里click here

示例树: 示例树: 顺序:4 2 5 1 6 3 7 预购:1 2 4 5 3 6 7 输出:4 6 11 12 18 21 28

Answer 1

int modify(struct node* node,int sum)
{
     if (node == NULL)
          return 0;

     int l=modify(node->left,sum);
     int r=modify(node->right,sum+l+node->data);

     int x=node->data;

     node->data=node->data+l+sum;

     return x+l+r;

}

使用语句调用函数:

modify(root,0);

完整实现:http://ideone.com/A3ezlk