binary-tree - resueltos - recorrido preorden arbol binario java

Algoritmo para imprimir todas las rutas con una suma dada en un árbol binario

Question

La siguiente es una pregunta de entrevista.

Se le proporciona un árbol binario (no necesariamente BST) en el que cada nodo contiene un valor. Diseñe un algoritmo para imprimir todas las rutas que sumen ese valor. Tenga en cuenta que puede ser cualquier ruta en el árbol, no tiene que comenzar en la raíz.

Aunque soy capaz de encontrar todas las rutas en el árbol que comienzan en la raíz con la suma dada, no puedo hacerlo para las rutas que no comienzan en la raíz.

Answer 1

A continuación se muestra la solución mediante recursión. Realizamos un recorrido en orden del árbol binario, a medida que bajamos un nivel, sumamos el peso total de la trayectoria agregando el peso del nivel actual a los pesos de los niveles anteriores del árbol. Si alcanzamos nuestra suma, imprimimos fuera del camino. Esta solución manejará casos en los que podemos tener más de 1 solución a lo largo de cualquier ruta de acceso determinada.

Supongamos que tiene un árbol binario enraizado en la raíz.

#include <iostream>
#include <vector>
using namespace std;
class Node
{
private:
Node* left;
Node* right;
int value;
public:
Node(const int value)
{
left=NULL;
right=NULL;
this->value=value;
}
void setLeft(Node* left)
{
this->left=left;
}
void setRight(Node* right)
{
this->right = right;
}
Node* getLeft() const
{
return left;
}
Node* getRight() const
{
return right;
}
const int& getValue() const
{
return value;
}
};
//get maximum height of the tree so we know how much space to allocate for our
//path vector
int getMaxHeight(Node* root)
{
if (root == NULL)
return 0;
int leftHeight = getMaxHeight(root->getLeft());
int rightHeight = getMaxHeight(root->getRight());
return max(leftHeight, rightHeight) + 1;
}
//found our target sum, output the path
void printPaths(vector<int>& paths, int start, int end)
{
for(int i = start; i<=end; i++)
cerr<<paths[i]<< " ";
cerr<<endl;
}
void generatePaths(Node* root, vector<int>& paths, int depth, const int sum)
{
//base case, empty tree, no path
if( root == NULL)
return;
paths[depth] = root->getValue();
int total =0;
//sum up the weights of the nodes in the path traversed
//so far, if we hit our target, output the path
for(int i = depth; i>=0; i--)
{
total += paths[i];
if(total == sum)
printPaths(paths, i, depth);
}
//go down 1 level where we will then sum up from that level
//back up the tree to see if any sub path hits our target sum
generatePaths(root->getLeft(), paths, depth+1, sum);
generatePaths(root->getRight(), paths, depth+1, sum);
}
int main(void)
{
vector<int> paths (getMaxHeight(&root));
generatePaths(&root, paths, 0,0);
}

la complejidad del espacio depende de la altura del árbol, asumiendo que este es un árbol equilibrado y la complejidad del espacio es 0 (log n) en función de la profundidad de la pila de recursión. Complejidad en el tiempo O (n Log n): se basa en un árbol equilibrado donde hay n nodos en cada nivel y en cada nivel n la cantidad de trabajo se realizará (sumando las rutas). También sabemos que la altura del árbol está delimitada por O (log n) para un árbol binario equilibrado, por lo que una cantidad de trabajo realizado para cada nivel en un árbol binario balanceado da un tiempo de ejecución de O (n log n)

Answer 2

Aquí hay un enfoque con complejidad nlogn .

1. Atraviesa el árbol con orden.
2. Al mismo tiempo, mantenga todos los nodos junto con la suma acumulada en un Hashmap<CumulativeSum, reference to the corresponding node> .
3. Ahora en un nodo determinado, calcule la suma acumulada desde la raíz hasta que el nodo diga que esto sea SUM .
4. Ahora busca el valor SUM-K en el HashMap .
5. Si la entrada existe, tome la referencia de nodo correspondiente en el HashMap .
6. Ahora tenemos una ruta válida desde la referencia del nodo al nodo actual.

Answer 3

Aquí hay una respuesta de O(n + numResults) (esencialmente la misma que la respuesta de @ Somebody, pero con todos los problemas resueltos):

1. Realice un recorrido previo, en orden o posterior al pedido del árbol binario.
2. A medida que realiza el recorrido, mantenga la suma acumulativa de valores de nodo desde el nodo raíz hasta el nodo sobre el nodo actual. Llamemos a este valor cumulativeSumBeforeNode .
3. Cuando visite un nodo en el recorrido, agréguelo a una tabla hash en cumulativeSumBeforeNode clave (el valor de esa clave será una lista de nodos).
4. Calcule la diferencia entre cumulativeSumBeforeNode y la suma objetivo. Busca esta diferencia en la tabla hash.
5. Si la búsqueda de la tabla hash tiene éxito, debería producir una lista de nodos. Cada uno de esos nodos representa el nodo de inicio de una solución. El nodo actual representa el nodo final para cada nodo de inicio correspondiente. Agregue cada combinación [nodo inicial, nodo final] a su lista de respuestas. Si la búsqueda de tabla hash falla, no haga nada.
6. Cuando haya terminado de visitar un nodo en el recorrido, elimine el nodo de la lista almacenada en key cumulativeSumBeforeNode en la tabla hash.

Código:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class BinaryTreePathsWithSum {
public static void main(String[] args) {
BinaryTreeNode a = new BinaryTreeNode(5);
BinaryTreeNode b = new BinaryTreeNode(16);
BinaryTreeNode c = new BinaryTreeNode(16);
BinaryTreeNode d = new BinaryTreeNode(4);
BinaryTreeNode e = new BinaryTreeNode(19);
BinaryTreeNode f = new BinaryTreeNode(2);
BinaryTreeNode g = new BinaryTreeNode(15);
BinaryTreeNode h = new BinaryTreeNode(91);
BinaryTreeNode i = new BinaryTreeNode(8);
BinaryTreeNode root = a;
a.left = b;
a.right = c;
b.right = e;
c.right = d;
e.left = f;
f.left = g;
f.right = h;
h.right = i;
/*
5
/ /
16 16
/ /
19 4
/
2
/ /
15 91
/
8
*/
List<BinaryTreePath> pathsWithSum = getBinaryTreePathsWithSum(root, 112); // 19 => 2 => 91
System.out.println(Arrays.toString(pathsWithSum.toArray()));
}
public static List<BinaryTreePath> getBinaryTreePathsWithSum(BinaryTreeNode root, int sum) {
if (root == null) {
throw new IllegalArgumentException("Must pass non-null binary tree!");
}
List<BinaryTreePath> paths = new ArrayList<BinaryTreePath>();
Map<Integer, List<BinaryTreeNode>> cumulativeSumMap = new HashMap<Integer, List<BinaryTreeNode>>();
populateBinaryTreePathsWithSum(root, 0, cumulativeSumMap, sum, paths);
return paths;
}
private static void populateBinaryTreePathsWithSum(BinaryTreeNode node, int cumulativeSumBeforeNode, Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int targetSum, List<BinaryTreePath> paths) {
if (node == null) {
return;
}
addToMap(cumulativeSumMap, cumulativeSumBeforeNode, node);
int cumulativeSumIncludingNode = cumulativeSumBeforeNode + node.value;
int sumToFind = cumulativeSumIncludingNode - targetSum;
if (cumulativeSumMap.containsKey(sumToFind)) {
List<BinaryTreeNode> candidatePathStartNodes = cumulativeSumMap.get(sumToFind);
for (BinaryTreeNode pathStartNode : candidatePathStartNodes) {
paths.add(new BinaryTreePath(pathStartNode, node));
}
}
populateBinaryTreePathsWithSum(node.left, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);
populateBinaryTreePathsWithSum(node.right, cumulativeSumIncludingNode, cumulativeSumMap, targetSum, paths);
removeFromMap(cumulativeSumMap, cumulativeSumBeforeNode);
}
private static void addToMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode, BinaryTreeNode node) {
if (cumulativeSumMap.containsKey(cumulativeSumBeforeNode)) {
List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
nodes.add(node);
} else {
List<BinaryTreeNode> nodes = new ArrayList<BinaryTreeNode>();
nodes.add(node);
cumulativeSumMap.put(cumulativeSumBeforeNode, nodes);
}
}
private static void removeFromMap(Map<Integer, List<BinaryTreeNode>> cumulativeSumMap, int cumulativeSumBeforeNode) {
List<BinaryTreeNode> nodes = cumulativeSumMap.get(cumulativeSumBeforeNode);
nodes.remove(nodes.size() - 1);
}
private static class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
public String toString() {
return this.value + "";
}
public int hashCode() {
return Integer.valueOf(this.value).hashCode();
}
public boolean equals(Object other) {
return this == other;
}
}
private static class BinaryTreePath {
public BinaryTreeNode start;
public BinaryTreeNode end;
public BinaryTreePath(BinaryTreeNode start, BinaryTreeNode end) {
this.start = start;
this.end = end;
}
public String toString() {
return this.start + " to " + this.end;
}
}
}

Answer 4

Basado en la respuesta de Christian arriba:

public void printSums(Node n, int sum, int currentSum, String buffer) {
if (n == null) {
return;
}
int newSum = currentSum + n.val;
String newBuffer = buffer + " " + n.val;
if (newSum == sum) {
System.out.println(newBuffer);
}
printSums(n.left, sum, newSum, newBuffer);
printSums(n.right, sum, newSum, newBuffer);
printSums(n.left, sum, 0, "");
printSums(n.right, sum, 0, "");
}
printSums(root, targetSum, 0, "");

Answer 5

Bueno, esto es un árbol, no un gráfico. Entonces, puedes hacer algo como esto:

Pseudocódigo

global ResultList
function ProcessNode(CurrentNode, CurrentSum)
CurrentSum+=CurrentNode->Value
if (CurrentSum==SumYouAreLookingFor) AddNodeTo ResultList
for all Children of CurrentNode
ProcessNode(Child,CurrentSum)

Bueno, esto te da los caminos que comienzan en la raíz. Sin embargo, puedes hacer un pequeño cambio:

 for all Children of CurrentNode
ProcessNode(Child,CurrentSum)
ProcessNode(Child,0)

Es posible que deba pensar en ello por un segundo (estoy ocupado con otras cosas), pero esto básicamente debería ejecutar el mismo algoritmo enraizado en cada nodo del árbol.

EDIT: esto en realidad le da al "nodo final" solamente. Sin embargo, como este es un árbol, puede comenzar en esos nodos finales y volver a subir hasta obtener la suma requerida.

EDIT 2: y, por supuesto, si todos los valores son positivos, puede abortar el descenso si su suma actual es> = la requerida

Answer 6

Buscar:

Recursively traverse the tree, comparing with the input key, as in binary search tree.
If the key is found, move the target node (where the key was found) to the root position using splaysteps.
Pseudocode:
Algorithm: search (key)
Input: a search-key
1. found = false;
2. node = recursiveSearch (root, key)
3. if found
4. Move node to root-position using splaysteps;
5. return value
6. else
7. return null
8. endif
Output: value corresponding to key, if found.
Algorithm: recursiveSearch (node, key)
Input: tree node, search-key
1. if key = node.key
2. found = true
3. return node
4. endif
// Otherwise, traverse further
5. if key < node.key
6. if node.left is null
7. return node
8. else
9. return recursiveSearch (node.left, key)
10. endif
11. else
12. if node.right is null
13. return node
14. else
15. return recursiveSearch (node.right, key)
16. endif
17. endif
Output: pointer to node where found; if not found, pointer to node for insertion.

Answer 7

He mejorado alguna lógica de codificación de respuesta por Arvind Upadhyay. Una vez realizado el bucle if, no se puede utilizar la misma lista. Así que hay que crear la nueva lista. Además, es necesario mantener el recuento del nivel que baja la lógica desde el nodo actual a la ruta de búsqueda. Si no encontramos el camino, así que antes de ir a sus hijos, debemos salir de la llamada recursiva igual para contar los tiempos.

int count =0;
public void printAllPathWithSum(Node node, int sum, ArrayList<Integer> list)
{
if(node == null)
return;
if(node.data<=sum)
{
list.add(node.data);
if(node.data == sum)
print(list);
else
{
count ++;
printAllPathWithSum(node.left, sum-node.data, list);
printAllPathWithSum(node.right, sum-node.data, list);
count --;
}
}
if(count != 0)
return ;
printAllPathWithSum(node.left, this.sum, new ArrayList());
if(count != 0)
return;
printAllPathWithSum(node.right, this.sum, new ArrayList());
}
public void print(List list)
{
System.out.println("Next path");
for(int i=0; i<list.size(); i++)
System.out.print(Integer.toString((Integer)list.get(i)) + " ");
System.out.println();
}

Verifique el código completo en: https://github.com/ganeshzilpe/java/blob/master/Tree/BinarySearchTree.java

Answer 8

Podemos resolverlo con programación dinámica de estructura de árbol, y tanto la complejidad de tiempo como de espacio es O (n ^ 2), donde n es el número de todos los nodos de árbol.

La idea es la siguiente:

Para un nodo de árbol, mantenemos un conjunto que registra todas las sumas posibles comenzando desde u hasta todos sus descendientes. Luego recursivamente, cualquier conjunto de nodos puede ser actualizado por sus dos hijos, específicamente, mediante la fusión de dos conjuntos de niños.

El pseudocódigo es:

bool findPath(Node u, Set uset, int finalSum) {
Set lset, rset;
if (findPath(u.left, lset, finalSum) || findPath(u.right, rset, finalSum)) return true;
for (int s1 : lset) {
if (finalSum - u.val - s1 == 0 || rset.contains(finalSum - u.val - s1)) return true;
// first condition means a path from u to some descendant in u''s left child
// second condition means a path from some node in u''s left child to some node in u''s right child
uset.insert(s1 + u.val); // update u''s set
}
for (int s2 : rset) {
if (finalSum - u.val - s2 == 0) return true;
// don''t forget the path from u to some descendant in u''s right child
uset.insert(s2 + u.val); // update u''s set
}
return false;
}

Me doy cuenta de que la pregunta original es encontrar todas las rutas, pero el algoritmo anterior es encontrar si existió. Creo que la idea es similar, pero esta versión hace que el problema sea más fácil de explicar :)

Answer 9

Una solución limpia en Java. Uso de llamadas recursivas internas para hacer un seguimiento de las rutas cruzadas.

private static void pathSunInternal(TreeNode root, int sum, List<List<Integer>> result, List<Integer> path){
if(root == null)
return;
path.add(root.val);
if(sum == root.val && root.left == null && root.right == null){
result.add(path);
}
else if(sum != root.val && root.left == null && root.right == null)
return;
else{
List<Integer> leftPath = new ArrayList<>(path);
List<Integer> rightPath = new ArrayList<>(path);
pathSunInternal(root.left, sum - root.val, result, leftPath);
pathSunInternal(root.right, sum - root.val, result, rightPath);
}
}
public static List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
pathSunInternal(root, sum, result, path);
return result;
}

Answer 10

Uno puede reducir este árbol a un gráfico ponderado G, donde cada peso de borde = suma de valores en cada uno de sus nodos.

Luego, ejecute el algoritmo Floyd-Warshall en el gráfico G. Al inspeccionar los elementos en la matriz resultante, podemos obtener todos los pares de nodos entre los cuales la suma total es igual a la suma deseada.

Además, tenga en cuenta que la ruta más corta que proporciona el algoritmo es también la única ruta entre 2 nodos en este árbol.

Este es solo otro enfoque, no tan eficiente como un enfoque recursivo.

Answer 11

Ya que necesitamos los caminos con suma == k. Supongo que la complejidad del peor de los casos puede ser O (total_paths_in_tree).

Entonces, ¿por qué no generar cada ruta y verificar la suma, de todos modos es un árbol con números negativos y ni siquiera es un árbol de búsqueda binario?

 struct node{
int val;
node *left,*right;
node(int vl)
{
val = vl;
left = NULL;
right = NULL;
}
};
vector<vector<int> > all_paths;
vector<vector<int> > gen_paths(node* root)
{
if(root==NULL)
{
return vector<vector<int> > ();
}
vector<vector<int> > left_paths = gen_paths(root->left);
vector<vector<int> > right_paths = gen_paths(root->right);
left_paths.push_back(vector<int> ()); //empty path
right_paths.push_back(vector<int> ());
vector<vector<int> > paths_here;
paths_here.clear();
for(int i=0;i<left_paths.size();i++)
{
for(int j=0;j<right_paths.size();j++)
{
vector<int> vec;
vec.clear();
vec.insert(vec.end(), left_paths[i].begin(), left_paths[i].end());
vec.push_back(root->val);
vec.insert(vec.end(), right_paths[j].begin(), right_paths[j].end());
paths_here.push_back(vec);
}
}
all_paths.insert(all_paths.end(),paths_here.begin(),paths_here.end());
vector<vector<int> > paths_to_extend;
paths_to_extend.clear();
for(int i=0;i<left_paths.size();i++)
{
paths_to_extend.push_back(left_paths[i]);
paths_to_extend[i].push_back(root->val);
}
for(int i=0;i<right_paths.size();i++)
{
paths_to_extend.push_back(right_paths[i]);
paths_to_extend[paths_to_extend.size()-1].push_back(root->val);
}
return paths_to_extend;
}

Para generar rutas, he generado todas las rutas a la izquierda y todas las rutas a la derecha Y agregué las rutas a la izquierda + nodo-> val + las rutas a la derecha en todas las rutas en cada nodo. Y han enviado las rutas que aún pueden extenderse. Es decir, todas las rutas desde ambos lados + nodo.

Answer 12

https://codereview.stackexchange.com/questions/74957/find-all-the-paths-of-tree-that-add-to-a-input-value

He intentado una respuesta, esperando la revisión del código. Mi código, así como los revisores, deberían ser una fuente útil.

Answer 13

Actualización: Ahora veo que mi respuesta no responde directamente a su pregunta. Lo dejaré aquí si resulta útil, pero no necesita votos positivos. Si no es útil, lo eliminaré. Estoy de acuerdo con @nhahtdh, sin embargo, cuando él aconseja, "Reutilice su algoritmo con todos los demás nodos como raíz".

Uno sospecha que el entrevistador está pescando para la recursión aquí. ¡No lo decepciones!

Dado un nodo, su rutina debe llamarse a sí misma contra cada uno de sus nodos secundarios, si tiene alguno, y luego agregar el propio dato del nodo a los valores de retorno, luego devolver la suma.

Para obtener crédito adicional, advierta al entrevistador que su rutina puede fallar, ingresando en una recursión sin fin, sin fondo, si se usa en un gráfico general en lugar de un árbol binario.

Answer 14

# include<stdio.h>
# include <stdlib.h>
struct Node
{
int data;
struct Node *left, *right;
};
struct Node * newNode(int item)
{
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void print(int p[], int level, int t){
int i;
for(i=t;i<=level;i++){
printf("/n%d",p[i]);
}
}
void check_paths_with_given_sum(struct Node * root, int da, int path[100], int level){
if(root == NULL)
return ;
path[level]=root->data;
int i;int temp=0;
for(i=level;i>=0;i--){
temp=temp+path[i];
if(temp==da){
print(path,level,i);
}
}
check_paths_with_given_sum(root->left, da, path,level+1);
check_paths_with_given_sum(root->right, da, path,level+1);
}
int main(){
int par[100];
struct Node *root = newNode(10);
root->left = newNode(2);
root->right = newNode(4);
root->left->left = newNode(1);
root->right->right = newNode(5);
check_paths_with_given_sum(root, 9, par,0);
}

Esto funciona.....

Answer 15

// assumption node have integer value other than zero
void printAllPaths(Node root, int sum , ArrayList<Integer> path) {
if(sum == 0) {
print(path); // simply print the arraylist
}
if(root ==null) {
//traversed one end of the tree...just return
return;
}
int data = root.data;
//this node can be at the start, end or in middle of path only if it is //less than the sum
if(data<=sum) {
list.add(data);
//go left and right
printAllPaths(root.left, sum-data , path);
printAllPaths(root.right, sum-data , path);
}
//note it is not else condition to ensure root can start from anywhere
printAllPaths(root.left, sum , path);
printAllPaths(root.right, sum , path);
}

Answer 16

public void printPath(N n) {
printPath(n,n.parent);
}
private void printPath(N n, N endN) {
if (n == null)
return;
if (n.left == null && n.right == null) {
do {
System.out.print(n.value);
System.out.print(" ");
} while ((n = n.parent)!=endN);
System.out.println("");
return;
}
printPath(n.left, endN);
printPath(n.right, endN);
}

Puede imprimir la ruta del árbol al final del nodo n. como esta printPath (n);

Answer 17

void printpath(int sum,int arr[],int level,struct node * root)
{
int tmp=sum,i;
if(root == NULL)
return;
arr[level]=root->data;
for(i=level;i>=0;i--)
tmp-=arr[i];
if(tmp == 0)
print(arr,level,i+1);
printpath(sum,arr,level+1,root->left);
printpath(sum,arr,level+1,root->right);
}
void print(int arr[],int end,int start)
{
int i;
for(i=start;i<=end;i++)
printf("%d ",arr[i]);
printf("/n");
}

complejidad (n logn) complejidad de espacio (n)