Dado un árbol de búsqueda binario que tiene N Nodes, la tarea es encontrar todos los caminos que comienzan en la raíz y terminan en cualquier hoja y que tienen una suma par.
Ejemplos:
Aporte:
Img-Btree
Salida:
sumas pares Las rutas son:
1st) 1 -> 19 -> 4 -> 9 -> 7 = sum(40)
2nd) 1 -> 19 -> 4 -> 9 -> 13 -> 18 -> 16 = sum (80)
3rd) 1 -> 19 -> 25 -> 35 = sum(68)
4th) 1 -> 19 -> 25 -> 23 = sum(80)
Explicación: Cuando comenzamos a atravesar desde el Node raíz hasta el Node hoja entonces tenemos camino diferente son (1, 19, 4, 9, 7), (1, 19, 4, 9, 13, 18, 16), (1, 19, 25, 35), (1, 19, 25 , 23) y (1, 19, 4, 2, 3). Y después de encontrar la suma de cada camino encontramos que todos son pares. Aquí encontramos un camino impar que es 1 -> 19 -> 4 -> 2 -> 3 = sum(29).Entrada: 2
/ \
1 3
Salida: Sin camino
Explicación: No hay camino que tenga una suma par.
Enfoque: El problema se puede resolver usando una pila , con base en la siguiente idea:
Recorre todo el árbol y sigue almacenando la ruta en la pila. Cuando se alcanza la hoja, compruebe si la suma de la ruta es par o no.
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Tome una pila (digamos ruta ) para almacenar la ruta actual .
- Atraviesa recursivamente el árbol y en cada iteración:
- Almacene la suma de todos los Nodes a lo largo de esta ruta (digamos sum ) y almacene los datos de ese Node en la ruta también.
- Traverse para el niño izquierdo.
- Traverse para el niño adecuado.
- Si se llega a un Node hoja, compruebe si la suma de la ruta es par o impar.
- Devolver todos esos caminos.
A continuación se muestra el código para entender mejor:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
int cnt;
// Structure of a tree node
class Node {
public:
Node* left;
int val;
Node* right;
Node(int val)
{
this->right = right;
this->val = val;
this->left = left;
}
};
// Function to print path
void print(stack<int> pth)
{
vector<int> v;
cout << "[";
while (!pth.empty()) {
v.push_back(pth.top());
pth.pop();
}
while (v.size() != 1) {
cout << v.back() << ",";
v.pop_back();
}
cout << v.back();
cout << "]";
}
// Function to find the paths
void cntEvenPath(Node* root, int sum, stack<int>& path)
{
// Add the value of node in sum
sum += root->val;
// Keep storing the node element
// in the path
path.push(root->val);
// If node has no left and right child
// and also the sum is even
// then return the path
if ((sum & 1) == 0
&& (root->left == NULL && root->right == NULL)) {
cnt++;
cout << "Sum Of ";
print(path);
cout << " = " << sum << "\n";
return;
}
// Check left child
if (root->left != NULL) {
cntEvenPath(root->left, sum, path);
path.pop();
}
// Check right child
if (root->right != NULL) {
cntEvenPath(root->right, sum, path);
path.pop();
}
}
// Driver code
int main()
{
// Build a tree
Node* root = new Node(1);
root->right = new Node(19);
root->right->right = new Node(25);
root->right->left = new Node(4);
root->right->left->left = new Node(2);
root->right->left->right = new Node(9);
root->right->right->left = new Node(23);
root->right->right->right = new Node(35);
root->right->left->left->right = new Node(3);
root->right->left->right->left = new Node(7);
root->right->left->right->right = new Node(13);
root->right->left->right->right->right = new Node(18);
root->right->left->right->right->right->left
= new Node(16);
cout << "\n";
// Stack to store path
stack<int> path;
cntEvenPath(root, 0, path);
if (cnt == 0)
cout << "No path";
return 0;
}
// This code is contributed by Rohit Pradhan
Java
// Java code to implement the approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
static int count = 0;
// Structure of a tree node
static class Node {
Node left;
int val;
Node right;
Node(int val)
{
this.right = right;
this.val = val;
this.left = left;
}
}
// Function to find the paths
static void cntEvenPath(Node root, int sum,
Stack<Integer> path)
{
// Add the value of node in sum
sum += root.val;
// Keep storing the node element
// in the path
path.push(root.val);
// If node has no left and right child
// and also the sum is even
// then return the path
if ((sum & 1) == 0
&& (root.left == null
&& root.right == null)) {
count++;
System.out.println("Sum Of"
+ path + " = "
+ sum);
return;
}
// Check left child
if (root.left != null) {
cntEvenPath(root.left, sum, path);
path.pop();
}
// Check right child
if (root.right != null) {
cntEvenPath(root.right, sum, path);
path.pop();
}
}
// Driver code
public static void main(String[] args)
{
// Build a tree
Node root = new Node(1);
root.right = new Node(19);
root.right.right = new Node(25);
root.right.left = new Node(4);
root.right.left.left = new Node(2);
root.right.left.right = new Node(9);
root.right.right.left = new Node(23);
root.right.right.right
= new Node(35);
root.right.left.left.right
= new Node(3);
root.right.left.right.left
= new Node(7);
root.right.left.right.right
= new Node(13);
root.right.left.right.right.right
= new Node(18);
root.right.left.right.right.right.left
= new Node(16);
System.out.println();
// Stack to store path
Stack<Integer> path = new Stack<>();
cntEvenPath(root, 0, path);
if (count == 0)
System.out.println("No path");
}
}
Python3
# Python code to implement the approach
# Node to create the tree
class Node:
def __init__(self, val):
self.right = None
self.val = val
self.left = None
# Function to find the paths
def cntEvenPath(root, sum, path):
# Add the value of node in sum
sum += root.val
# Keep storing the node element
# in the path
path.append(root.val)
# If node has no left and right child
# and also the sum is even
# then return the path
if ((sum & 1) == 0 and root.left == None and root.right == None):
global count
count += 1
print("Sum Of", path, " = ", sum)
return
# Check left child
if (root.left != None):
cntEvenPath(root.left, sum, path)
path.pop()
# Check right child
if (root.right != None):
cntEvenPath(root.right, sum, path)
path.pop()
count = 0
# Defining main function
def main():
# Build a tree
root = Node(1)
root.right = Node(19)
root.right.right = Node(25)
root.right.left = Node(4)
root.right.left.left = Node(2)
root.right.left.right = Node(9)
root.right.right.left = Node(23)
root.right.right.right = Node(35)
root.right.left.left.right = Node(3)
root.right.left.right.left = Node(7)
root.right.left.right.right = Node(13)
root.right.left.right.right.right = Node(18)
root.right.left.right.right.right.left = Node(16)
# Stack to store path
path = []
cntEvenPath(root, 0, path)
if (count == 0):
print("No path")
if __name__ == "__main__":
main()
# This code is contributed by jainlovely450
C#
// C# code to implement the approach
using System;
using System.Collections;
public class GFG {
static int count = 0;
// Structure of a tree node
class Node {
public Node left;
public int val;
public Node right;
public Node(int val)
{
this.right = null;
this.val = val;
this.left = null;
}
}
// Function to find the paths
static void cntEvenPath(Node root, int sum, Stack path)
{
// Add the value of node in sum
sum += root.val;
// Keep storing the node element
// in the path
path.Push(root.val);
// If node has no left and right child
// and also the sum is even
// then return the path
if ((sum & 1) == 0
&& (root.left == null && root.right == null)) {
count++;
Console.Write("Sum Of [");
Object[] arr = path.ToArray();
for (int i = arr.Length - 1; i >= 0; i--) {
if (i == 0) {
Console.Write(arr[i]);
break;
}
Console.Write(arr[i] + ",");
}
Console.WriteLine("] = " + sum);
return;
}
// Check left child
if (root.left != null) {
cntEvenPath(root.left, sum, path);
path.Pop();
}
// Check right child
if (root.right != null) {
cntEvenPath(root.right, sum, path);
path.Pop();
}
}
static public void Main()
{
// Build a tree
Node root = new Node(1);
root.right = new Node(19);
root.right.right = new Node(25);
root.right.left = new Node(4);
root.right.left.left = new Node(2);
root.right.left.right = new Node(9);
root.right.right.left = new Node(23);
root.right.right.right = new Node(35);
root.right.left.left.right = new Node(3);
root.right.left.right.left = new Node(7);
root.right.left.right.right = new Node(13);
root.right.left.right.right.right = new Node(18);
root.right.left.right.right.right.left
= new Node(16);
Console.WriteLine();
// Stack to store path
Stack path = new Stack();
cntEvenPath(root, 0, path);
if (count == 0)
Console.WriteLine("No path");
}
}
// This code is contributed by lokesh(lokeshmvs21).
Producción
Sum Of [1,19,4,9,7] = 40 Sum Of [1,19,4,9,13,18,16] = 80 Sum Of [1,19,25,23] = 68 Sum Of [1,19,25,35] = 80
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por madhav_mohan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA