Transformar a Suma Árbol

En este artículo, vamos a ver cómo convertir un árbol binario de árbol de suma ? Este problema ha aparecido en Amazon, Microsoft.

Planteamiento del problema: Dado un árbol binario en el que cada nodo tiene valores positivos y negativos. Convertir a un árbol donde cada nodo contiene la suma de los árboles sub izquierdo y derecho en el árbol original. Los valores de nodos hoja se cambian a 0.

Ejemplo:

For example, the following tree
10
/
-2 8
/ /
6 -5 -7 5
Should be converted to:
5(1-2-2+8)
/
1(6-5) -2(-7+5)
/ /
0 0 0 0

árbol Sum

A se dice árbol binario para ser convertido en el árbol de suma:

  1. Todos los nodos hoja son convertido a 0
  2. Todos los nodos tienen la suma de subárbol derecho y subárbol izquierdo en el árbol original

Consideremos,

para cualquier nodo intermedio que tiene dos hijos en orden k nivel

Valor del nodo debe ser actualizado como

suma de subárbol derecho del nodo + suma de subárbol izquierdo del nodo

Ahora consideran tanto el derecho y hijo izquierdo ha sido ya convertidos a sus valores de nodo de actualización que tienen respectivas sumas de subárbol hasta (k + 1) -ésimo nivel (de abajo a (k + 1) -ésimo nivel).

Por lo tanto el valor del nodo debe ser actualizada como: el valor hijo derecho sumas + hijo izquierdo valor + subárbol hasta (k + 1) nivel

= valor viejo hijo derecho + valor viejo hijo izquierdo + nuevo hijo izquierdo valor (suma de subárboles hasta (k + 1) nivel) nuevo valor hijo derecho (suma de subárboles hasta (k + 1) nivel) +.

lo tanto, aquí podemos desarrollar nuestra función recursiva para desarrollar el algo

FUNCTION toSumTree (node)
1. Check base case
IF (node==NULL)
Return 0;
2. Store old value of node
3. Update node value to left subtree sum + right
subtree sum. Use recursion to find subtree sums
4. Return old node value + current node value for
upper levels ( towards root)
END FUNCTION

implementación en C ++ para transformar a Suma árbol

#include <bits/stdc++.h>
using namespace std;
// tree node is defined
class tree{
public:
int data;
tree *left;
tree *right;
};
//convert to sum tree
int toSumTree(tree *node){
if(!node) //base case
return 0;
//store old value
int temp=node->data;
//update to new value
node->data=toSumTree(node->left)+toSumTree(node->right);
//return for upper level sums
return node->data+temp;
}
//printing the tree using level order traversal
void printTree(tree* root){
queue<tree*> q; // using stl
tree* temp;
q.push(root);
q.push(NULL);
cout<<"rootn";
while(!q.empty()){
temp=q.front();
q.pop();
if(temp==NULL){
if(!q.empty()){
cout<<"nnext leveln";
q.push(NULL);
}
}
else{
cout<<temp->data<<" "; //print node
if(temp->left)
q.push(temp->left); //EnQueue
if(temp->right)
q.push(temp->right); //EnQueue
}
}
}
// creating new node
tree* newnode(int data)
{
tree* node = (tree*)malloc(sizeof(tree));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
//**same tree is builted as shown in example**
cout<<"same tree is built as shown in examplen";
tree *root=newnode(10);
root->left= newnode(-2);
root->right= newnode(8);
root->right->right=newnode(5);
root->right->left=newnode(-7);
root->left->left=newnode(6);
root->left->right=newnode(-5);
cout<<"printing the original tree...n";
printTree(root);
toSumTree(root);
cout<<"nprinting the converted tree...n";
printTree(root);
return 0;
}

salida

same tree is built as shown in example
printing the original tree...
root
10
next level
-2 8
next level
6 -5 -7 5
printing the converted tree...
root
5
next level
1 -2
next level
0 0 0 0

Explicación con ejemplo:

vamos a ver cómo la función resuelve el ejemplo anterior.

Original tree:
10
/
-2 8
/ /
6 -5 -7 5
In the main function it calls toSumTree (10)
------------------------------------------------------------
toSumTree (10) //call at Main()
node is not NULL
temp=10
new node value = toSumTree (10->left) + toSumTree (10->right)
=toSumTree (-2) + toSumTree (8)
Thus call to toSumTree (-2) and toSumTree (8)
Return new node value + temp (10)
------------------------------------------------------------
toSumTree (-2) //call at toSumTree (10)
node is not NULL
temp=-2
new node value = toSumTree (-2->left) + toSumTree (-2->right)
=toSumTree (6) + toSumTree (-5)
Thus call to toSumTree (6) and toSumTree (-5)
Return new node value + temp (-2)
------------------------------------------------------------
toSumTree (8) //call at toSumTree (10)
node is not NULL
temp=8
new node value = toSumTree (8->left) + toSumTree (8->right)
=toSumTree (-7) + toSumTree (5)
Thus call to toSumTree (-7) and toSumTree (5)
Return new node value + temp (8)
------------------------------------------------------------
toSumTree (6) //call at toSumTree (-2)
node is not NULL
temp=6
new node value = toSumTree (6->left) + toSumTree (6->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (6)
------------------------------------------------------------
toSumTree (-5) //call at toSumTree (-2)
node is not NULL
temp=-5
new node value = toSumTree (-5->left) + toSumTree (-5->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (-5)
------------------------------------------------------------
toSumTree (-7)//call at toSumTree(8)
node is not NULL
temp=-7
new node value = toSumTree (-7->left) + toSumTree (-7->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (-7)
------------------------------------------------------------
toSumTree (5)//call at toSumTree (8)
node is not NULL
temp=5
new node value = toSumTree (5->left) + toSumTree (5->right)
=toSumTree (NULL) + toSumTree (NULL)
Thus call to toSumTree (NULL) and toSumTree (NULL)
Return new node value + temp (5)
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(6)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree (6)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(-5)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(-5)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(-7)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(-7)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(5)
node is NULL
return 0
------------------------------------------------------------
toSumTree (NULL)//call at toSumTree(5)
node is NULL
return 0
At toSumTree (6) //call at toSumTree(-2)
new node value = toSumTree (6->left) + toSumTree (6->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
6->0
It returns 0+6=6
------------------------------------------------------------
At toSumTree (-5) //call at toSumTree(-2)
new node value = toSumTree (-5->left) + toSumTree (-5->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
-5->0
It returns 0-5=-5
------------------------------------------------------------
At toSumTree (-7) //call at toSumTree(8)
new node value = toSumTree (-7->left) + toSumTree (-7->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
-7->0
It returns 0-7=-7
------------------------------------------------------------
At toSumTree (5) //call at toSumTree (8)
new node value = toSumTree (5->left) + toSumTree (5->right)
=toSumTree (NULL) + toSumTree (NULL)
=0
5->0
It returns 0+5=5
------------------------------------------------------------
At toSumTree (-2) //call at toSumTree(10)
new node value = toSumTree (-2->left) + toSumTree (-2->right)
=toSumTree (6) + toSumTree (-5)
=6 + (-5) =1
-2->1
It returns -2+1=-1
------------------------------------------------------------
At toSumTree (8) //call at toSumTree (10)
new node value = toSumTree (-8->left) + toSumTree (-8->right)
=toSumTree (-7) + toSumTree (5)
=-7 + (5) =-2
8->-2
It returns -2+8=6
------------------------------------------------------------
At toSumTree (10) //call at main
new node value = toSumTree (10->left) + toSumTree (10->right)
=toSumTree (-2) + toSumTree (8)
=-1 + 6=5
10->5
It returns 10+5=15
So, the binary tree is sum converted to:
5
/
1 -2
/ /
0 0 0 0


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *