Dado un árbol binario, la tarea es encontrar la suma de todos los Nodes cuyo padre es par.
Ejemplos:
Input: 1 / \ 3 8 / \ 5 6 / 1 Output: 11 The only even nodes are 8 and 6 and the sum of their children is 5 + 6 = 11. Input: 2 / \ 3 8 / / \ 2 5 6 / \ 1 3 Output: 25 3 + 8 + 5 + 6 + 3 = 25
Enfoque: Inicialice sum = 0 y realice un recorrido recursivo del árbol y verifique si el Node es par o no, si el Node es par, agregue los valores de sus hijos a la suma. Finalmente, imprima la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // A binary tree node struct Node { int data; struct Node *left, *right; }; // A utility function to allocate a new node struct Node* newNode(int data) { struct Node* newNode = new Node; newNode->data = data; newNode->left = newNode->right = NULL; return (newNode); } // This function visit each node in preorder fashion // And adds the values of the children of a node with // even value to the res variable void calcSum(Node* root, int& res) { // Base Case if (root == NULL) return; // If the value of the // current node if even if (root->data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root->left) res += root->left->data; // Do the same with the right child if (root->right) res += root->right->data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root->left, res); calcSum(root->right, res); } // Function to return the sum of nodes // whose parent has even value int findSum(Node* root) { // Initialize result int res = 0; calcSum(root, res); return res; } // Driver code int main() { // Creating the tree struct Node* root = newNode(2); root->left = newNode(3); root->right = newNode(8); root->left->left = newNode(2); root->right->left = newNode(5); root->right->right = newNode(6); root->right->left->left = newNode(1); root->right->right->right = newNode(3); // Print the required sum cout << findSum(root); return 0; }
Java
// Java implementation of the approach class GFG { // A binary tree node static class Node { int data; Node left, right; }; static int res; // A utility function to allocate a new node static Node newNode(int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode); } // This function visit each node in preorder fashion // And adds the values of the children of a node with // even value to the res variable static void calcSum(Node root) { // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right); } // Function to return the sum of nodes // whose parent has even value static int findSum(Node root) { // Initialize result res = 0; calcSum(root); return res; } // Driver code public static void main(String[] args) { // Creating the tree Node root = newNode(2); root.left = newNode(3); root.right = newNode(8); root.left.left = newNode(2); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(1); root.right.right.right = newNode(3); // Print the required sum System.out.print(findSum(root)); } } // This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach result = 0; # A binary tree node class Node : def __init__(self,data) : self.data = data; self.left = None self.right = None; # This function visit each node in preorder fashion # And adds the values of the children of a node with # even value to the res variable def calcSum(root, res) : global result; # Base Case if (root == None) : return; # If the value of the # current node if even if (root.data % 2 == 0) : # If the left child of the even # node exist then add it to the res if (root.left) : res += root.left.data; result = res; # Do the same with the right child if (root.right) : res += root.right.data; result = res; # Visiting the left subtree and the right # subtree just like preorder traversal calcSum(root.left, res); calcSum(root.right, res); # Function to return the sum of nodes # whose parent has even value def findSum(root) : res = 0; calcSum(root, res); print(result) # Driver code if __name__ == "__main__" : # Creating the tree root = Node(2); root.left = Node(3); root.right = Node(8); root.left.left = Node(2); root.right.left = Node(5); root.right.right = Node(6); root.right.left.left = Node(1); root.right.right.right = Node(3); # Print the required sum findSum(root); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach using System; class GFG { // A binary tree node class Node { public int data; public Node left, right; }; static int res; // A utility function to allocate a new node static Node newNode(int data) { Node newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode); } // This function visit each node in preorder fashion // And adds the values of the children of a node with // even value to the res variable static void calcSum(Node root) { // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right); } // Function to return the sum of nodes // whose parent has even value static int findSum(Node root) { // Initialize result res = 0; calcSum(root); return res; } // Driver code public static void Main(String[] args) { // Creating the tree Node root = newNode(2); root.left = newNode(3); root.right = newNode(8); root.left.left = newNode(2); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(1); root.right.right.right = newNode(3); // Print the required sum Console.Write(findSum(root)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript implementation of the approach // A binary tree node class Node { constructor() { this.data = 0; this.left = null; this.right = null; } }; var res = 0; // A utility function to allocate a new node function newNode(data) { var newNode = new Node(); newNode.data = data; newNode.left = newNode.right = null; return (newNode); } // This function visit each node in preorder fashion // And adds the values of the children of a node with // even value to the res variable function calcSum(root) { // Base Case if (root == null) return; // If the value of the // current node if even if (root.data % 2 == 0) { // If the left child of the even // node exist then add it to the res if (root.left != null) res += root.left.data; // Do the same with the right child if (root.right != null) res += root.right.data; } // Visiting the left subtree and the right // subtree just like preorder traversal calcSum(root.left); calcSum(root.right); } // Function to return the sum of nodes // whose parent has even value function findSum(root) { // Initialize result res = 0; calcSum(root); return res; } // Driver code // Creating the tree var root = newNode(2); root.left = newNode(3); root.right = newNode(8); root.left.left = newNode(2); root.right.left = newNode(5); root.right.right = newNode(6); root.right.left.left = newNode(1); root.right.right.right = newNode(3); // Print the required sum document.write(findSum(root)); </script>
Producción:
25
Complejidad de tiempo: O(n) donde n es el número de Nodes en el árbol binario dado.