Páratlan számú részfák száma
Adott egy bináris fa, keresse meg a páratlan számú részfák számát.
Példák:
Input : 2 / 1 3 / / 4 10 8 5 / 6 Output : 6 The subtrees are 4 6 1 8 3 / / 4 10 8 5 / 6 2 / 1 3 / / 4 10 8 5 / 6
Az ötlet az, hogy rekurzívan áthaladunk a fán. Minden csomóponthoz rekurzívan számolja meg a páros számokat a bal és a jobb oldali részfákban. Ha a gyökér is páros, akkor add hozzá azt is a számláláshoz. Ha a szám páratlanná válik, akkor az eredmény.
count = 0 // Initialize result int countSubtrees(root) { if (root == NULL) return 0; // count even numbers in left subtree int c = countSubtrees(root-> left); // Add count of even numbers in right subtree c += countSubtrees(root-> right); // check if root data is an even number if (root-> data % 2 == 0) c += 1; // If total count of even numbers // for the subtree is odd if (c % 2 != 0) count++; // return total count of even // numbers of the subtree return c; } Végrehajtás:
C++ // C++ implementation to find number of // subtrees having odd count of even numbers #include using namespace std ; /* A binary tree Node */ struct Node { int data ; struct Node * left * right ; }; /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */ struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ); } // Returns count of subtrees having odd count of // even numbers int countRec ( struct Node * root int * pcount ) { // base condition if ( root == NULL ) return 0 ; // count even nodes in left subtree int c = countRec ( root -> left pcount ); // Add even nodes in right subtree c += countRec ( root -> right pcount ); // Check if root data is an even number if ( root -> data % 2 == 0 ) c += 1 ; // if total count of even numbers // for the subtree is odd if ( c % 2 != 0 ) ( * pcount ) ++ ; // Total count of even nodes of the subtree return c ; } // A wrapper over countRec() int countSubtrees ( Node * root ) { int count = 0 ; int * pcount = & count ; countRec ( root pcount ); return count ; } // Driver program to test above int main () { // binary tree formation struct Node * root = newNode ( 2 ); /* 2 */ root -> left = newNode ( 1 ); /* / */ root -> right = newNode ( 3 ); /* 1 3 */ root -> left -> left = newNode ( 4 ); /* / / */ root -> left -> right = newNode ( 10 ); /* 4 10 8 5 */ root -> right -> left = newNode ( 8 ); /* / */ root -> right -> right = newNode ( 5 ); /* 6 */ root -> left -> right -> left = newNode ( 6 ); cout < < 'Count = ' < < countSubtrees ( root ); return 0 ; } // This code is contributed by famously.
C // C implementation to find number of // subtrees having odd count of even numbers #include /* A binary tree Node */ struct Node { int data ; struct Node * left * right ; }; /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */ struct Node * newNode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ); } // Returns count of subtrees having odd count of // even numbers int countRec ( struct Node * root int * pcount ) { // base condition if ( root == NULL ) return 0 ; // count even nodes in left subtree int c = countRec ( root -> left pcount ); // Add even nodes in right subtree c += countRec ( root -> right pcount ); // Check if root data is an even number if ( root -> data % 2 == 0 ) c += 1 ; // if total count of even numbers // for the subtree is odd if ( c % 2 != 0 ) ( * pcount ) ++ ; // Total count of even nodes of the subtree return c ; } // A wrapper over countRec() int countSubtrees ( Node * root ) { int count = 0 ; int * pcount = & count ; countRec ( root pcount ); return count ; } // Driver program to test above int main () { // binary tree formation struct Node * root = newNode ( 2 ); /* 2 */ root -> left = newNode ( 1 ); /* / */ root -> right = newNode ( 3 ); /* 1 3 */ root -> left -> left = newNode ( 4 ); /* / / */ root -> left -> right = newNode ( 10 ); /* 4 10 8 5 */ root -> right -> left = newNode ( 8 ); /* / */ root -> right -> right = newNode ( 5 ); /* 6 */ root -> left -> right -> left = newNode ( 6 ); printf ( 'Count = %d' countSubtrees ( root )); return 0 ; }
Java // Java implementation to find number of // subtrees having odd count of even numbers import java.util.* ; class GfG { /* A binary tree Node */ static class Node { int data ; Node left right ; } /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */ static Node newNode ( int data ) { Node node = new Node (); node . data = data ; node . left = null ; node . right = null ; return ( node ); } // Returns count of subtrees having odd count of // even numbers static class P { int pcount = 0 ; } static int countRec ( Node root P p ) { // base condition if ( root == null ) return 0 ; // count even nodes in left subtree int c = countRec ( root . left p ); // Add even nodes in right subtree c += countRec ( root . right p ); // Check if root data is an even number if ( root . data % 2 == 0 ) c += 1 ; // if total count of even numbers // for the subtree is odd if ( c % 2 != 0 ) ( p . pcount ) ++ ; // Total count of even nodes of the subtree return c ; } // A wrapper over countRec() static int countSubtrees ( Node root ) { P p = new P (); countRec ( root p ); return p . pcount ; } // Driver program to test above public static void main ( String [] args ) { // binary tree formation Node root = newNode ( 2 ); /* 2 */ root . left = newNode ( 1 ); /* / */ root . right = newNode ( 3 ); /* 1 3 */ root . left . left = newNode ( 4 ); /* / / */ root . left . right = newNode ( 10 ); /* 4 10 8 5 */ root . right . left = newNode ( 8 ); /* / */ root . right . right = newNode ( 5 ); /* 6 */ root . left . right . left = newNode ( 6 ); System . out . println ( 'Count = ' + countSubtrees ( root )); } }
Python3 # Python3 implementation to find number of # subtrees having odd count of even numbers # Helper class that allocates a new Node # with the given data and None left and # right pointers. class newNode : def __init__ ( self data ): self . data = data self . left = self . right = None # Returns count of subtrees having odd # count of even numbers def countRec ( root pcount ): # base condition if ( root == None ): return 0 # count even nodes in left subtree c = countRec ( root . left pcount ) # Add even nodes in right subtree c += countRec ( root . right pcount ) # Check if root data is an even number if ( root . data % 2 == 0 ): c += 1 # if total count of even numbers # for the subtree is odd if c % 2 != 0 : pcount [ 0 ] += 1 # Total count of even nodes of # the subtree return c # A wrapper over countRec() def countSubtrees ( root ): count = [ 0 ] pcount = count countRec ( root pcount ) return count [ 0 ] # Driver Code if __name__ == '__main__' : # binary tree formation root = newNode ( 2 ) # 2 root . left = newNode ( 1 ) # / root . right = newNode ( 3 ) # 1 3 root . left . left = newNode ( 4 ) # / / root . left . right = newNode ( 10 ) # 4 10 8 5 root . right . left = newNode ( 8 ) # / root . right . right = newNode ( 5 ) # 6 root . left . right . left = newNode ( 6 ) print ( 'Count = ' countSubtrees ( root )) # This code is contributed by PranchalK
C# // C# implementation to find number of // subtrees having odd count of even numbers using System ; class GFG { /* A binary tree Node */ public class Node { public int data ; public Node left right ; } /* Helper function that allocates a new Node with the given data and NULL left and right pointers. */ static Node newNode ( int data ) { Node node = new Node (); node . data = data ; node . left = null ; node . right = null ; return ( node ); } // Returns count of subtrees // having odd count of even numbers public class P { public int pcount = 0 ; } static int countRec ( Node root P p ) { // base condition if ( root == null ) return 0 ; // count even nodes in left subtree int c = countRec ( root . left p ); // Add even nodes in right subtree c += countRec ( root . right p ); // Check if root data is an even number if ( root . data % 2 == 0 ) c += 1 ; // if total count of even numbers // for the subtree is odd if ( c % 2 != 0 ) ( p . pcount ) ++ ; // Total count of even nodes of the subtree return c ; } // A wrapper over countRec() static int countSubtrees ( Node root ) { P p = new P (); countRec ( root p ); return p . pcount ; } // Driver Code public static void Main ( String [] args ) { // binary tree formation Node root = newNode ( 2 ); /* 2 */ root . left = newNode ( 1 ); /* / */ root . right = newNode ( 3 ); /* 1 3 */ root . left . left = newNode ( 4 ); /* / / */ root . left . right = newNode ( 10 ); /* 4 10 8 5 */ root . right . left = newNode ( 8 ); /* / */ root . right . right = newNode ( 5 ); /* 6 */ root . left . right . left = newNode ( 6 ); Console . WriteLine ( 'Count = ' + countSubtrees ( root )); } } // This code is contributed by 29AjayKumar
JavaScript < script > // Javascript implementation to find number of // subtrees having odd count of even numbers // A binary tree Node class Node { // Helper function that allocates a new // Node with the given data and NULL left // and right pointers. constructor ( data ) { this . data = data ; this . left = this . right = null ; } } // Returns count of subtrees having odd // count of even numbers class P { constructor () { this . pcount = 0 ; } } function countRec ( root p ) { // Base condition if ( root == null ) return 0 ; // Count even nodes in left subtree let c = countRec ( root . left p ); // Add even nodes in right subtree c += countRec ( root . right p ); // Check if root data is an even number if ( root . data % 2 == 0 ) c += 1 ; // If total count of even numbers // for the subtree is odd if ( c % 2 != 0 ) ( p . pcount ) ++ ; // Total count of even nodes // of the subtree return c ; } // A wrapper over countRec() function countSubtrees ( root ) { let p = new P (); countRec ( root p ); return p . pcount ; } // Driver code // Binary tree formation let root = new Node ( 2 ); /* 2 */ root . left = new Node ( 1 ); /* / */ root . right = new Node ( 3 ); /* 1 3 */ root . left . left = new Node ( 4 ); /* / / */ root . left . right = new Node ( 10 ); /* 4 10 8 5 */ root . right . left = new Node ( 8 ); /* / */ root . right . right = new Node ( 5 ); /* 6 */ root . left . right . left = new Node ( 6 ); document . write ( 'Count = ' + countSubtrees ( root ) + '
' ); // This code is contributed by rag2127 < /script>
Kimenet
Count = 6
Időbeli összetettség: O(n) // ahol n a bináris fa csomópontjainak száma.
A tér összetettsége: On)
Kvíz létrehozása
