Dado un árbol binario , calcule la suma de Nodes con abuelos pares.
Ejemplos:
Input: 22 / \ 3 8 / \ / \ 4 8 1 9 \ 2 Output: 24 Explanation The nodes 4, 8, 2, 1, 9 has even value grandparents. Hence sum = 4 + 8 + 1 + 9 + 2 = 24. Input: 1 / \ 2 3 / \ / \ 4 5 6 7 / 8 Output: 8 Explanation Only 8 has 2 as a grandparent.
Enfoque: para resolver el problema mencionado anteriormente, para cada Node que no sea nulo, verifique si tienen un abuelo y si su abuelo es incluso valorado, agregue los datos del Node a la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find sum // of all the child nodes with // even grandparents in a Binary Tree #include <bits/stdc++.h> using namespace std; /* A binary tree node has data and pointers to the right and left children*/ struct TreeNode { int data; TreeNode *left, *right; TreeNode(int x) { data = x; left = right = NULL; } }; // Function to calculate the sum void getSum( TreeNode* curr, TreeNode* p, TreeNode* gp, int& sum) { // Base condition if (curr == NULL) return; // Check if node has a grandparent // if it does check // if they are even valued if (gp != NULL && gp->data % 2 == 0) sum += curr->data; // Recurse for left child getSum(curr->left, curr, p, sum); // Recurse for right child getSum(curr->right, curr, p, sum); } // Driver Program int main() { TreeNode* root = new TreeNode(22); root->left = new TreeNode(3); root->right = new TreeNode(8); root->left->left = new TreeNode(4); root->left->right = new TreeNode(8); root->right->left = new TreeNode(1); root->right->right = new TreeNode(9); root->right->right->right = new TreeNode(2); int sum = 0; getSum(root, NULL, NULL, sum); cout << sum << '\n'; return 0; }
Java
// Java implementation to find sum // of all the child nodes with // even grandparents in a Binary Tree import java.util.*; class GFG{ /* A binary tree node has data and pointers to the right and left children*/ static class TreeNode { int data; TreeNode left, right; TreeNode(int x) { data = x; left = right = null; } } static int sum = 0; // Function to calculate the sum static void getSum(TreeNode curr, TreeNode p, TreeNode gp) { // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p); } // Driver Program public static void main(String[] args) { TreeNode root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); System.out.println(sum); } } // This code is contributed by Rajput-Ji
Python3
# Python3 implementation to find sum # of all the child nodes with # even grandparents in a Binary Tree # A binary tree node has data and # pointers to the right and left children class TreeNode(): def __init__(self, data): self.data = data self.left = None self.right = None sum = 0 # Function to calculate the sum def getSum(curr, p, gp): global sum # Base condition if (curr == None): return # Check if node has a grandparent # if it does check # if they are even valued if (gp != None and gp.data % 2 == 0): sum += curr.data # Recurse for left child getSum(curr.left, curr, p) # Recurse for right child getSum(curr.right, curr, p) # Driver code if __name__=="__main__": root = TreeNode(22) root.left = TreeNode(3) root.right = TreeNode(8) root.left.left = TreeNode(4) root.left.right = TreeNode(8) root.right.left = TreeNode(1) root.right.right = TreeNode(9) root.right.right.right = TreeNode(2) getSum(root, None, None) print(sum) # This code is contributed by rutvik_56
C#
// C# implementation to find sum // of all the child nodes with // even grandparents in a Binary Tree using System; class GFG{ /* A binary tree node has data and pointers to the right and left children*/ class TreeNode { public int data; public TreeNode left, right; public TreeNode(int x) { data = x; left = right = null; } } static int sum = 0; // Function to calculate the sum static void getSum(TreeNode curr, TreeNode p, TreeNode gp) { // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p); } // Driver Program public static void Main(String[] args) { TreeNode root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); Console.WriteLine(sum); } } // This code is contributed by Princi Singh
Javascript
<script> // JavaScript implementation to find sum // of all the child nodes with // even grandparents in a Binary Tree /* A binary tree node has data and pointers to the right and left children*/ class TreeNode { constructor(x) { this.left = null; this.right = null; this.data = x; } } let sum = 0; // Function to calculate the sum function getSum(curr, p, gp) { // Base condition if (curr == null) return; // Check if node has // a grandparent // if it does check // if they are even valued if (gp != null && gp.data % 2 == 0) sum += curr.data; // Recurse for left child getSum(curr.left, curr, p); // Recurse for right child getSum(curr.right, curr, p); } let root = new TreeNode(22); root.left = new TreeNode(3); root.right = new TreeNode(8); root.left.left = new TreeNode(4); root.left.right = new TreeNode(8); root.right.left = new TreeNode(1); root.right.right = new TreeNode(9); root.right.right.right = new TreeNode(2); getSum(root, null, null); document.write(sum); </script>
Producción:
24
Complejidad de tiempo: O(N)
Complejidad de espacio: O(H) , Utilizado por la pila de recursión donde H = altura del árbol.
Publicación traducida automáticamente
Artículo escrito por AnshulVerma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA