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>
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