ritrovamento somma massima possibile accordo triangolare

Question

Sto avendo un albero binario

  2 
    / \ 
     3  4 
    /\  \ 
    5 1  8 
/\  /\ 
    1 6  9 2 
       \ 
        4 

voglio trovare il maximum possible triangular chord info sum di nodi (tra due foglie e un nodo con entrambi i bambini a destra ea sinistra) nella struttura di data .

un accordo triangolare sarà

per accordo triangolare:

solo immaginare una linea tra due foglie, vanno verso l'alto in direzione della radice, trovare un genitore comune (che può essere genitore, nonno, grandgrandparent o addirittura la radice stessa). Mentre si muove verso l'alto, per ogni foglia (per ogni foglia o dobbiamo andare solo verso sinistra e sinistra sinistra ... e così OR o solo destra destra destra destra ... e così) significa (la foglia sinistra si muoverà solo verso l'alto solo right e la foglia destra si sposterà solo verso l'interno left ..... Quindi per ogni singola foglia, we can not move in both direction while moving upwards) .. Ora otteniamo una forma triangolare .. in cui a side may contain any no. of nodes/links possible .. ORA, se questo triangular shape does not contain any extra internal branches. quella forma triangolare sarà una corda triangolare.

ricordo che every leaf node is also always a triangular chord (E 'solo per creare i casi di default, se l'albero binario non hanno alcuna triangolare corda a forma)

ora

maximum triangular chord will be that triangular chord 
which have maximum total in sum of all its node info. 

ci viene richiesto di return that maximum total.

If we do not have triangular shaped chord.. 
then we have to return the leaf with maximum info. 

per esempio

8      
/\ 
2 3 
     \ 
     3 

è un accordo triangolare

8      
/\     
2 3 
    \ \ 
    4 1 

sottoalbero solo singolo nodo 4 sarà corda massima triangolare (come somma è maggiore di un altro accordo triangolare con singolo nodo 1) Non tutto l'albero sarà accordo triangolare

8      
/\ 
    2 3 
/ \ 
4  3 

è un accordo triangolare

così la soluzione del primo albero sulla prima linea di domanda è

8+9+2+4 = 23 

sono intrappolato in questo problema.

Ho un approccio grezzo

io ricorsivamente chiamare leftchild come radice della sottostruttura e trova fianco massima somma accordo triangolare quindi uguale per rightchild come radice della sottostruttura.

aggiungere il massimo di leftmax e rightmax, e la aggiunge al nodo Rood e tornare

in C++ mycode è:

int maxtri(node* n) 
{ 
    if(n) 
    { 
    lsum = maxtri(n->left); 
    rsum = maxtri(n->right); 
    k = maxof(lsum,rsum); 
    return (n->info + k); 
    } 
} 

edit: il mio un altro approccio ricorsivo

int l =0, r =0; 
int maxtri(node* n) 
{ 
if (n == NULL) return 0; 
if (!(n->left) && !(n->right)) return n->info; 
if ((n->left) && (n->right)) 
{ 
    l = maxtri(n->left); 
    r = maxtri(n->right); 
} 
if ((n->left) && !(n->right)) 
{ 
    l = l + maxtri(n->left); 
} 
if (!(n->left) && (n->right)) 
{ 
    r = r + maxtri(n->right); 
} 
return (l+r+n->info); 
} 

i avere dubbi sul mio approccio.

qualcuno può dare un'altra soluzione?

Answer 1

Che dire di questa logica:
Per ogni nodo traversa la parte sinistra e la parte destra, se si scopre che rami allora non prendere in considerazione questo nodo nel calcolo altro considerare questo. Inoltre, per la parte del calcolo il nodo avrebbe dovuto lasciare i nodi giusti & o dovrebbe essere il nodo foglia.

Nota: non l'ho provato correttamente ma credo che dovrebbe funzionare.

// Node by Node traverse the tree 

void addSum(Node *head, vector<int>& sum) 
{ 
if (head == NULL) 
    return; 
else { 
    int s = traverseThisNode(head); 
    sum.push_back(s); // Add to vector 
    addSum(head->left, sum); 
    addSum(head->right, sum); 
} 
} 

// For each node traverse left & right 

int traverseThisNode(Node *head) 
{ 
if (head && head->left && head->right) { 
    Node *temp = head; // To traverse right portion of this node 
    int sum = head->value; 
    while(head->left) { // Traverse right 
     head = head->left; 
     sum = sum + head->value; 
     if (head->right) { // Condition to check if there is any branching 
      sum = 0; 
      break; 
     } 
    } 
    while(temp->right && sum != 0) { // Traverse Right now 
     temp = temp->right; 
     sum = sum + temp->value; 
     if (temp->left) { // Condition to check if there is any branching 
      sum = 0; 
      break; 
     } 
    } 

    return sum; 
} else if (head && !head->left && !head->right) { 
    return head->value; // To add leaf node 
} 
return 0; 
} 

Now you have vector containing all the value of triangular in the tree, traverse it and 
find the maximum. 
int maximum() 
{ 
    // Traverse the vector "sum" & find the maximum 
} 

Answer 2

Scrivo lo pseudocodice per il mio approccio, per quanto ho capito la domanda.

Max = min_value; //possibly 0 if no negative value is allowed for nodes. 
sum = 0; 
for each node in the tree 
    temp = node; 
    sum+= temp->data //collects data at the current level, the current level may be leaf too. 
    Until temp->left is not null, // Traversing uni-directionally to the left most deep and collecting data. 
     temp = temp->left 
     sum+=temp->data 
    Until temp->right is not null, // Traversing uni-directionally to the right most deep and collecting data. 
     temp = temp->right 
     sum+= temp->data 

    if(sum > Max) 
     Max = sum; 

    sum = 0; 



print Max;