c++ - 交替符号的二叉树

Question

给定一棵具有以下属性的二叉树，它的所有叶节点都处于正号 (+)，然后符号交替直到该路径的根。因此，根据路径，节点可以有多个符号。

现在我们需要找出每条路径的总和以及整个树的总和。

for ex:
there are 5 paths in the given binary tree.

path 1: 10-2+3-4 = 7

path 2: 19-8+2-3+4 = 14

path 3: 12-11+17-3+4 = 19

path 4: 2-9+1-4 = -10

path 5: 21-9+1-4 = 9


overall sum 39

这里的问题是确定每个节点的符号，这些节点由其基础路径中的叶节点管理。

我可以想到一个具有 O(n) 时间复杂度和 O(n) 空间的解决方案，我可以将每条路径保存在从根到底部遍历的 vector 中，然后确定从叶节点开始的每个节点的符号，从而计算总和每条路径。

现在任何人都可以提出任何改进的方法，空间复杂度为 O(1)。任何递归或迭代方法将是首选。

我希望我已经清楚地解释了这个问题。不过，如果出现任何疑问，我会尽快添加更多详细信息。

编辑:二叉树是这样存储和实现的，而不是在数组中

struct node
{
    int data;
    struct node* left;
    struct node* right;
};

struct node* newNode(int data)

{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5); 
}

存放树所需要的空间是无论如何都省不下来的。请不要制作这棵树。假设您已获得一棵树的根节点，并且已经构建了树。

我说的是运行特定算法来回答问题所需的额外空间。

Answer 1

好的，所以，如果我们可以从下到上遍历树，我们可以很容易地获得具有 O(1) 额外空间和 O(n^2) 时间复杂度的解决方案:

for(every leaf in tree){

   Node node = leaf;
   int total = 0;
   int sign = 1;
   while(node != null){
       total += sign*node.value;
       node = node.parent;
       sign *= -1; 
   }
   print total;
}

对于O(n)时间复杂度的自上而下遍历，要获得O(1)的额外空间，需要更复杂的算法

Node node = root;
Node last = null;
int total = 0;
int sign = 1;
boolean back = false;
while(node != null){
     total += sign*node.value;
     if(node is leaf){
        if(sign == 1)
           print total;//Need to check if sign is not positive
        else
           print -total;
        back = true;//If this is leaf, we need to go back
        total -= sign*node.value;
        last = node;
        node = node.parent;
     }else if(back){
        if(last is left child){
           back = false;
           node = node.rightChild;
        }else{//We need to continue to go back if we are going back and this is right child 
           last = node;
           total -= sign*node.value;
           node = node.parent;
        } 
     }else{
        total += sign*node.value;
        node = node.leftChild;
     }
     sign *= -1; 

}

注意:

• 递归自上而下遍历或使用堆栈的迭代遍历很容易产生 O(n) 空间复杂度，所以要小心!

• 没有每个节点中的父链接，我们无法解决这个问题，因为在这种情况下，需要一个类似堆栈的数据结构来遍历树。

更新:

因为我们可以改变树中节点的值，所以我们可以修改节点的左链接以将其用作到父节点的链接。

Node node = root;
Node last = null;
int total = 0;
int sign = 1;
boolean back = false;
while(node != null){
     total += sign*node.value;
     if(node is leaf){
        if(sign == 1)
           print total;//Need to check if sign is not positive
        else
           print -total;
        back = true;//If this is leaf, we need to go back
        total -= sign*node.value;
        Node tmp = last;//For leaf node, we can just use variable last
        last = node;
        node = tmp;
     }else if(back){
        if(last is not right child){
           back = false;
           last = node;
           node = node.rightChild;
        }else{//We need to continue to go back if we are going back and this is right child 
           last = node;
           total -= sign*node.value;
           node = node.leftChild;
        } 
     }else{
        total += sign*node.value;
        Node tmp = node.leftChild;
        node.leftChild = last;
        last = node;
        node = tmp;
     }
     sign *= -1; 

}