Двоичное дерево с переменным знаком

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), где я мог бы сохранять каждый путь в векторном перемещении от корня до нижнего &, затем определяя знак каждого узла, начиная с листового узла, вычисляя таким образом сумма каждого пути.

Теперь любой может предложить какой-либо улучшенный метод с сложностью пространства O (1). Любой из рекурсивного или итерационного метода будет предпочтительнее.

Надеюсь, что я четко объяснил вопрос. Тем не менее, если возникнут какие-либо сомнения, я скоро добавлю больше деталей.

EDIT: бинарное дерево хранится & реализована как этот & не в массиве

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), поэтому будьте осторожны!

• Без родительской ссылки в каждом узле мы не можем решить эту проблему, так как в этом случае для перемещения по дереву требуется структура данных, подобная стеку.

Update:

Как мы можем изменить значение узла в дереве, так что мы можем изменить левую ссылку узла, чтобы использовать его в качестве ссылки на родительский узел.

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; 

}