Dado un árbol binario , la tarea es imprimir todas las rutas posibles de raíz a hoja que tengan un número máximo de Nodes con valores pares.
Ejemplos:
Aporte:
2 / \ 6 3 / \ \ 4 7 11 / \ \ 10 12 1Salida:
2 -> 6 -> 4 -> 10
2 -> 6 -> 4 -> 12
Explicación:
Recuento de Nodes pares en la ruta 2 -> 6 -> 4 -> 10 = 4
Recuento de Nodes pares en la ruta 2 -> 6 -> 4 -> 12 = 4
Cantidad de Nodes pares en la ruta 2 -> 6 -> 7 -> 1 = 2
Cantidad de Nodes pares en la ruta 2 -> 3 -> 11 = 1
Por lo tanto, el las rutas que consisten en el recuento máximo de Nodes pares son {2 -> 6 -> 4 -> 10} y {2 -> 6 -> 4 -> 12}.Aporte:
5 / \ 6 3 / \ \ 4 9 2Salida: 5 -> 6 -> 4.
Enfoque: El problema se puede resolver usando Preorder Traversal . La idea es atravesar el árbol binario dado y encontrar el máximo número posible de Nodes pares en un camino de raíz a hoja. Finalmente, recorra el árbol e imprima todas las rutas posibles de raíz a hoja que tengan el número máximo de Nodes pares. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos cntMaxEven y cntEven para almacenar el recuento máximo de Nodes pares desde la raíz hasta un Node hoja y el recuento de Nodes pares desde la raíz hasta un Node hoja.
- Atraviese el árbol y verifique las siguientes condiciones:
- Compruebe si el Node actual es un Node hoja y cntEven > cntMaxEven o no. Si se determina que es cierto, actualice cntMaxEven = cntEven .
- De lo contrario, verifique si el Node actual es un Node par o no. Si se determina que es cierto, actualice cntEven += 1 .
- Finalmente, recorra el árbol e imprima todas las rutas posibles de raíz a hoja con un recuento de Nodes pares igual a cntMaxEven .
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of the binary tree
struct Node {
// Stores data
int data;
// Stores left child
Node* left;
// Stores right child
Node* right;
// Initialize a node
// of binary tree
Node(int val)
{
// Update data;
data = val;
left = right = NULL;
}
};
// Function to find maximum count
// of even nodes in a path
int cntMaxEvenNodes(Node* root)
{
// If the tree is an
// empty binary tree.
if (root == NULL) {
return 0;
}
// Stores count of even nodes
// in current subtree
int cntEven = 0;
// If root node is
// an even node
if (root->data % 2
== 0) {
// Update cntEven
cntEven += 1;
}
// Stores count of even nodes
// in left subtree.
int X = cntMaxEvenNodes(
root->left);
// Stores count of even nodes
// in right subtree.
int Y = cntMaxEvenNodes(
root->right);
// cntEven
cntEven += max(X, Y);
return cntEven;
}
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
void printPath(Node* root, int cntEven,
int cntMaxEven,
vector<int>& path)
{
// If the tree is an
// empty Binary Tree
if (root == NULL) {
return;
}
// If current node value is even
if (root->data % 2 == 0) {
path.push_back(
root->data);
cntEven += 1;
}
// If current node is
// a leaf node
if (root->left == NULL
&& root->right == NULL) {
// If count of even nodes in
// path is equal to cntMaxEven
if (cntEven == cntMaxEven) {
// Stores length of path
int N = path.size();
// Print path
for (int i = 0; i < N - 1;
i++) {
cout << path[i] << " -> ";
}
cout << path[N - 1] << endl;
}
}
// Left subtree
printPath(root->left, cntEven,
cntMaxEven, path);
// Right subtree
printPath(root->right, cntEven,
cntMaxEven, path);
// If current node is even
if (root->data % 2 == 0) {
path.pop_back();
// Update cntEven
cntEven--;
}
}
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
void printMaxPath(Node* root)
{
// Stores maximum count of even
// nodes of a path in the tree
int cntMaxEven;
cntMaxEven
= cntMaxEvenNodes(root);
// Stores path of tree having
// even nodes
vector<int> path;
printPath(root, 0, cntMaxEven,
path);
}
// Driver code
int main()
{
// Create tree.
Node* root = NULL;
root = new Node(2);
root->left = new Node(6);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(7);
root->right->right = new Node(11);
root->left->left->left = new Node(10);
root->left->left->right = new Node(12);
root->left->right->right = new Node(1);
printMaxPath(root);
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of the binary tree
static class Node
{
// Stores data
int data;
// Stores left child
Node left;
// Stores right child
Node right;
// Initialize a node
// of binary tree
Node(int val)
{
// Update data;
data = val;
left = right = null;
}
};
// Function to find maximum count
// of even nodes in a path
static int cntMaxEvenNodes(Node root)
{
// If the tree is an
// empty binary tree.
if (root == null)
{
return 0;
}
// Stores count of even nodes
// in current subtree
int cntEven = 0;
// If root node is
// an even node
if (root.data % 2 == 0)
{
// Update cntEven
cntEven += 1;
}
// Stores count of even nodes
// in left subtree.
int X = cntMaxEvenNodes(root.left);
// Stores count of even nodes
// in right subtree.
int Y = cntMaxEvenNodes(root.right);
// cntEven
cntEven += Math.max(X, Y);
return cntEven;
}
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
static void printPath(Node root, int cntEven,
int cntMaxEven,
Vector<Integer> path)
{
// If the tree is an
// empty Binary Tree
if (root == null)
{
return;
}
// If current node value is even
if (root.data % 2 == 0)
{
path.add(root.data);
cntEven += 1;
}
// If current node is
// a leaf node
if (root.left == null &&
root.right == null)
{
// If count of even nodes in
// path is equal to cntMaxEven
if (cntEven == cntMaxEven)
{
// Stores length of path
int N = path.size();
// Print path
for(int i = 0; i < N - 1; i++)
{
System.out.print(path.get(i) + " -> ");
}
System.out.print(path.get(N - 1) + "\n");
}
}
// Left subtree
printPath(root.left, cntEven,
cntMaxEven, path);
// Right subtree
printPath(root.right, cntEven,
cntMaxEven, path);
// If current node is even
if (root.data % 2 == 0)
{
path.remove(path.size() - 1);
// Update cntEven
cntEven--;
}
}
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
static void printMaxPath(Node root)
{
// Stores maximum count of even
// nodes of a path in the tree
int cntMaxEven;
cntMaxEven = cntMaxEvenNodes(root);
// Stores path of tree having
// even nodes
Vector<Integer> path = new Vector<>();
printPath(root, 0, cntMaxEven,
path);
}
// Driver code
public static void main(String[] args)
{
// Create tree.
Node root = null;
root = new Node(2);
root.left = new Node(6);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(7);
root.right.right = new Node(11);
root.left.left.left = new Node(10);
root.left.left.right = new Node(12);
root.left.right.right = new Node(1);
printMaxPath(root);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement # the above approach # Structure of the binary tree class newNode: def __init__(self, val): self.data = val self.left = None self.right = None path = [] # Function to find maximum count # of even nodes in a path def cntMaxEvenNodes(root): # If the tree is an # empty binary tree. if (root == None): return 0 # Stores count of even nodes # in current subtree cntEven = 0 # If root node is # an even node if (root.data % 2 == 0): # Update cntEven cntEven += 1 # Stores count of even nodes # in left subtree. X = cntMaxEvenNodes(root.left) # Stores count of even nodes # in right subtree. Y = cntMaxEvenNodes(root.right) # cntEven cntEven += max(X, Y) return cntEven # Function to print paths having # count of even nodes equal # to maximum count of even nodes def printPath(root, cntEven, cntMaxEven): global path # If the tree is an # empty Binary Tree if (root == None): return # If current node value is even if (root.data % 2 == 0): path.append(root.data) cntEven += 1 # If current node is # a leaf node if (root.left == None and root.right == None): # If count of even nodes in # path is equal to cntMaxEven if (cntEven == cntMaxEven): # Stores length of path N = len(path) # Print path for i in range(N - 1): print(path[i], end = "->") print(path[N - 1]) # Left subtree printPath(root.left, cntEven, cntMaxEven) # Right subtree printPath(root.right, cntEven, cntMaxEven) # If current node is even if (root.data % 2 == 0): path.remove(path[len(path) - 1]) # Update cntEven cntEven -= 1 # Utility Function to print path # from root to leaf node having # maximum count of even nodes def printMaxPath(root): global path # Stores maximum count of even # nodes of a path in the tree cntMaxEven = cntMaxEvenNodes(root) printPath(root, 0, cntMaxEven) # Driver code if __name__ == '__main__': # Create tree. root = None root = newNode(2) root.left = newNode(6) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(7) root.right.right = newNode(11) root.left.left.left = newNode(10) root.left.left.right = newNode(12) root.left.right.right = newNode(1) printMaxPath(root) # This code is contributed by bgangwar59
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of the binary tree
class Node
{
// Stores data
public int data;
// Stores left child
public Node left;
// Stores right child
public Node right;
// Initialize a node
// of binary tree
public Node(int val)
{
// Update data;
data = val;
left = right = null;
}
};
// Function to find maximum count
// of even nodes in a path
static int cntMaxEvenNodes(Node root)
{
// If the tree is an
// empty binary tree.
if (root == null)
{
return 0;
}
// Stores count of even
// nodes in current subtree
int cntEven = 0;
// If root node is
// an even node
if (root.data % 2 == 0)
{
// Update cntEven
cntEven += 1;
}
// Stores count of even
// nodes in left subtree.
int X = cntMaxEvenNodes(root.left);
// Stores count of even nodes
// in right subtree.
int Y = cntMaxEvenNodes(root.right);
// cntEven
cntEven += Math.Max(X, Y);
return cntEven;
}
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
static void printPath(Node root,
int cntEven,
int cntMaxEven,
List<int> path)
{
// If the tree is an
// empty Binary Tree
if (root == null)
{
return;
}
// If current node value
// is even
if (root.data % 2 == 0)
{
path.Add(root.data);
cntEven += 1;
}
// If current node is
// a leaf node
if (root.left == null &&
root.right == null)
{
// If count of even nodes in
// path is equal to cntMaxEven
if (cntEven == cntMaxEven)
{
// Stores length of path
int N = path.Count;
// Print path
for(int i = 0;
i < N - 1; i++)
{
Console.Write(path[i] +
" -> ");
}
Console.Write(path[N - 1] +
"\n");
}
}
// Left subtree
printPath(root.left, cntEven,
cntMaxEven, path);
// Right subtree
printPath(root.right, cntEven,
cntMaxEven, path);
// If current node is even
if (root.data % 2 == 0)
{
path.RemoveAt(path.Count - 1);
// Update cntEven
cntEven--;
}
}
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
static void printMaxPath(Node root)
{
// Stores maximum count of even
// nodes of a path in the tree
int cntMaxEven;
cntMaxEven = cntMaxEvenNodes(root);
// Stores path of tree having
// even nodes
List<int> path = new List<int>();
printPath(root, 0,
cntMaxEven, path);
}
// Driver code
public static void Main(String[] args)
{
// Create tree.
Node root = null;
root = new Node(2);
root.left = new Node(6);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(7);
root.right.right = new Node(11);
root.left.left.left = new Node(10);
root.left.left.right = new Node(12);
root.left.right.right = new Node(1);
printMaxPath(root);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of the binary tree
class Node
{
constructor(val)
{
this.left = null;
this.right = null;
this.data = val;
}
}
// Function to find maximum count
// of even nodes in a path
function cntMaxEvenNodes(root)
{
// If the tree is an
// empty binary tree.
if (root == null)
{
return 0;
}
// Stores count of even nodes
// in current subtree
let cntEven = 0;
// If root node is
// an even node
if (root.data % 2 == 0)
{
// Update cntEven
cntEven += 1;
}
// Stores count of even nodes
// in left subtree.
let X = cntMaxEvenNodes(root.left);
// Stores count of even nodes
// in right subtree.
let Y = cntMaxEvenNodes(root.right);
// cntEven
cntEven += Math.max(X, Y);
return cntEven;
}
// Function to print paths having
// count of even nodes equal
// to maximum count of even nodes
function printPath(root, cntEven,
cntMaxEven, path)
{
// If the tree is an
// empty Binary Tree
if (root == null)
{
return;
}
// If current node value is even
if (root.data % 2 == 0)
{
path.push(root.data);
cntEven += 1;
}
// If current node is
// a leaf node
if (root.left == null &&
root.right == null)
{
// If count of even nodes in
// path is equal to cntMaxEven
if (cntEven == cntMaxEven)
{
// Stores length of path
let N = path.length;
// Print path
for(let i = 0; i < N - 1; i++)
{
document.write(path[i] + " -> ");
}
document.write(path[N - 1] + "</br>");
}
}
// Left subtree
printPath(root.left, cntEven,
cntMaxEven, path);
// Right subtree
printPath(root.right, cntEven,
cntMaxEven, path);
// If current node is even
if (root.data % 2 == 0)
{
path.pop();
// Update cntEven
cntEven--;
}
}
// Utility Function to print path
// from root to leaf node having
// maximum count of even nodes
function printMaxPath(root)
{
// Stores maximum count of even
// nodes of a path in the tree
let cntMaxEven;
cntMaxEven = cntMaxEvenNodes(root);
// Stores path of tree having
// even nodes
let path = [];
printPath(root, 0, cntMaxEven, path);
}
// Driver code
// Create tree.
let root = null;
root = new Node(2);
root.left = new Node(6);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(7);
root.right.right = new Node(11);
root.left.left.left = new Node(10);
root.left.left.right = new Node(12);
root.left.right.right = new Node(1);
printMaxPath(root);
// This code is contributed by suresh07
</script>
Producción:
2 -> 6 -> 4 -> 10 2 -> 6 -> 4 -> 12
Complejidad temporal: O(N), donde N es el número de Nodes del árbol binario.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por deepanshujindal634 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA