Cea mai lungă secvență consecutivă din arborele binar
Încercați-l pe GfG Practice 
#practiceLinkDiv { display: none !important; }
Ieșire
#practiceLinkDiv { display: none !important; } Având în vedere un Arbore Binar, găsiți lungimea celei mai lungi căi care cuprinde noduri cu valori consecutive în ordine crescătoare. Fiecare nod este considerat ca o cale de lungime 1.
Exemple:
In below diagram binary tree with longest consecutive path(LCP) are shown :
Putem rezolva problema de mai sus recursiv. La fiecare nod avem nevoie de informații despre nodul său părinte, dacă nodul curent are o valoare mai mare decât nodul părinte, atunci face o cale consecutivă la fiecare nod, vom compara valoarea nodului cu valoarea părinte și vom actualiza în consecință cea mai lungă cale consecutivă.
Pentru a obține valoarea nodului părinte, vom trece (node_value + 1) ca argument la metoda recursivă și vom compara valoarea nodului cu această valoare a argumentului dacă satisface, actualizați lungimea curentă a căii consecutive, altfel reinițializam lungimea curentă a căii cu 1.
Vă rugăm să vedeți codul de mai jos pentru o mai bună înțelegere:
C++ // C/C++ program to find longest consecutive // sequence in binary tree #include using namespace std ; /* A binary tree node has data pointer to left child and a pointer to right child */ struct Node { int data ; Node * left * right ; }; // A utility function to create a node Node * newNode ( int data ) { Node * temp = new Node ; temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } // Utility method to return length of longest // consecutive sequence of tree void longestConsecutiveUtil ( Node * root int curLength int expected int & res ) { if ( root == NULL ) return ; // if root data has one more than its parent // then increase current length if ( root -> data == expected ) curLength ++ ; else curLength = 1 ; // update the maximum by current length res = max ( res curLength ); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil ( root -> left curLength root -> data + 1 res ); longestConsecutiveUtil ( root -> right curLength root -> data + 1 res ); } // method returns length of longest consecutive // sequence rooted at node root int longestConsecutive ( Node * root ) { if ( root == NULL ) return 0 ; int res = 0 ; // call utility method with current length 0 longestConsecutiveUtil ( root 0 root -> data res ); return res ; } // Driver code to test above methods int main () { Node * root = newNode ( 6 ); root -> right = newNode ( 9 ); root -> right -> left = newNode ( 7 ); root -> right -> right = newNode ( 10 ); root -> right -> right -> right = newNode ( 11 ); printf ( '%d n ' longestConsecutive ( root )); return 0 ; }
Java // Java program to find longest consecutive // sequence in binary tree class Node { int data ; Node left right ; Node ( int item ) { data = item ; left = right = null ; } } class Result { int res = 0 ; } class BinaryTree { Node root ; // method returns length of longest consecutive // sequence rooted at node root int longestConsecutive ( Node root ) { if ( root == null ) return 0 ; Result res = new Result (); // call utility method with current length 0 longestConsecutiveUtil ( root 0 root . data res ); return res . res ; } // Utility method to return length of longest // consecutive sequence of tree private void longestConsecutiveUtil ( Node root int curlength int expected Result res ) { if ( root == null ) return ; // if root data has one more than its parent // then increase current length if ( root . data == expected ) curlength ++ ; else curlength = 1 ; // update the maximum by current length res . res = Math . max ( res . res curlength ); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil ( root . left curlength root . data + 1 res ); longestConsecutiveUtil ( root . right curlength root . data + 1 res ); } // Driver code public static void main ( String args [] ) { BinaryTree tree = new BinaryTree (); tree . root = new Node ( 6 ); tree . root . right = new Node ( 9 ); tree . root . right . left = new Node ( 7 ); tree . root . right . right = new Node ( 10 ); tree . root . right . right . right = new Node ( 11 ); System . out . println ( tree . longestConsecutive ( tree . root )); } } // This code is contributed by shubham96301
Python3 # Python3 program to find longest consecutive # sequence in binary tree # A utility class to create a node class newNode : def __init__ ( self data ): self . data = data self . left = self . right = None # Utility method to return length of # longest consecutive sequence of tree def longestConsecutiveUtil ( root curLength expected res ): if ( root == None ): return # if root data has one more than its # parent then increase current length if ( root . data == expected ): curLength += 1 else : curLength = 1 # update the maximum by current length res [ 0 ] = max ( res [ 0 ] curLength ) # recursively call left and right subtree # with expected value 1 more than root data longestConsecutiveUtil ( root . left curLength root . data + 1 res ) longestConsecutiveUtil ( root . right curLength root . data + 1 res ) # method returns length of longest consecutive # sequence rooted at node root def longestConsecutive ( root ): if ( root == None ): return 0 res = [ 0 ] # call utility method with current length 0 longestConsecutiveUtil ( root 0 root . data res ) return res [ 0 ] # Driver Code if __name__ == '__main__' : root = newNode ( 6 ) root . right = newNode ( 9 ) root . right . left = newNode ( 7 ) root . right . right = newNode ( 10 ) root . right . right . right = newNode ( 11 ) print ( longestConsecutive ( root )) # This code is contributed by PranchalK
C# // C# program to find longest consecutive // sequence in binary tree using System ; class Node { public int data ; public Node left right ; public Node ( int item ) { data = item ; left = right = null ; } } class Result { public int res = 0 ; } class GFG { Node root ; // method returns length of longest consecutive // sequence rooted at node root int longestConsecutive ( Node root ) { if ( root == null ) return 0 ; Result res = new Result (); // call utility method with current length 0 longestConsecutiveUtil ( root 0 root . data res ); return res . res ; } // Utility method to return length of longest // consecutive sequence of tree private void longestConsecutiveUtil ( Node root int curlength int expected Result res ) { if ( root == null ) return ; // if root data has one more than its parent // then increase current length if ( root . data == expected ) curlength ++ ; else curlength = 1 ; // update the maximum by current length res . res = Math . Max ( res . res curlength ); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil ( root . left curlength root . data + 1 res ); longestConsecutiveUtil ( root . right curlength root . data + 1 res ); } // Driver code public static void Main ( String [] args ) { GFG tree = new GFG (); tree . root = new Node ( 6 ); tree . root . right = new Node ( 9 ); tree . root . right . left = new Node ( 7 ); tree . root . right . right = new Node ( 10 ); tree . root . right . right . right = new Node ( 11 ); Console . WriteLine ( tree . longestConsecutive ( tree . root )); } } // This code is contributed by 29AjayKumar
JavaScript < script > // JavaScript program to find longest consecutive // sequence in binary tree class Node { constructor ( item ) { this . data = item ; this . left = this . right = null ; } } let res = 0 ; let root ; function longestConsecutive ( root ) { if ( root == null ) return 0 ; res = [ 0 ]; // call utility method with current length 0 longestConsecutiveUtil ( root 0 root . data res ); return res [ 0 ]; } // Utility method to return length of longest // consecutive sequence of tree function longestConsecutiveUtil ( root curlength expected res ) { if ( root == null ) return ; // if root data has one more than its parent // then increase current length if ( root . data == expected ) curlength ++ ; else curlength = 1 ; // update the maximum by current length res [ 0 ] = Math . max ( res [ 0 ] curlength ); // recursively call left and right subtree with // expected value 1 more than root data longestConsecutiveUtil ( root . left curlength root . data + 1 res ); longestConsecutiveUtil ( root . right curlength root . data + 1 res ); } // Driver code root = new Node ( 6 ); root . right = new Node ( 9 ); root . right . left = new Node ( 7 ); root . right . right = new Node ( 10 ); root . right . right . right = new Node ( 11 ); document . write ( longestConsecutive ( root )); // This code is contributed by rag2127 < /script>
Ieșire
3
Complexitatea timpului: O(N) unde N este numărul de noduri dintr-un arbore binar dat.
Spațiu auxiliar: O(log(N))
De asemenea, discutat pe link-ul de mai jos:
Lungimea maximă consecutivă de creștere a căii în arbore binar
Creați un test
