Niiden alipuiden lukumäärä, joissa on pariton määrä parillisia lukuja
Hae binääripuusta niiden alipuiden lukumäärä, joilla on pariton määrä parillisia lukuja.
Esimerkkejä:
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
Ajatuksena on kulkea rekursiivisesti puun poikki. Laske jokaiselle solmulle rekursiivisesti parilliset luvut vasemmassa ja oikeassa alipuussa. Jos root on myös parillinen, lisää se myös laskeaksesi. Jos määrästä tulee pariton, lisäys tulos.
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; } Toteutus:
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>
Lähtö
Count = 6
Aika monimutkaisuus: O(n) // missä n on binääripuun solmujen lukumäärä.
Avaruuden monimutkaisuus: O(n)
Luo tietokilpailu
