Suurin peräkkäinen kasvava polun pituus binääripuussa
Määritä binääripuulla pisimmän polun pituus, joka koostuu solmuista, joilla on peräkkäiset arvot kasvavassa järjestyksessä. Jokaista solmua pidetään poluna, jonka pituus on 1.
Esimerkkejä:
10 / / 11 9 / / / / 13 12 13 8 Maximum Consecutive Path Length is 3 (10 11 12) Note : 10 9 8 is NOT considered since the nodes should be in increasing order. 5 / / 8 11 / / 9 10 / / / / 6 15 Maximum Consecutive Path Length is 2 (8 9).
Jokainen binaaripuun solmu voi joko tulla osaksi polkua, joka alkaa yhdestä sen pääsolmusta, tai uusi polku voi alkaa tästä solmusta itsestään. Tärkeintä on löytää rekursiivisesti vasemman ja oikean alipuun polun pituus ja palauttaa sitten maksimi. Jotkut tapaukset on otettava huomioon puun poikki kulkiessa, joita käsitellään alla.
- Ed : tallentaa pääsolmun arvon. Alusta prev yhdellä juursolmun arvolla, jotta juuresta alkavan polun pituus voi olla vähintään 1.
- vain : Tallentaa polun pituuden, joka päättyy parhaillaan vieraillun solmun yläpäähän.
Tapaus 1 : Nykyisen solmun arvo on edellinen +1
Suurenna tässä tapauksessa polun pituutta yhdellä ja etsi sitten rekursiivisesti vasemman ja oikean alipuun polun pituus ja palauta sitten kahden pituuden välinen maksimi.
Tapaus 2 : Nykyisen solmun arvo EI ole edellinen+1
Tästä solmusta voi alkaa uusi polku, joten etsi rekursiivisesti vasemman ja oikean alipuun polun pituus. Polku, joka päättyy nykyisen solmun pääsolmuun, voi olla suurempi kuin polku, joka alkaa tästä solmusta. Ota siis maksimi polku, joka alkaa tästä solmusta ja päättyy edelliseen solmuun.
Alla yllä olevan idean toteutus.
C++ // C++ Program to find Maximum Consecutive // Path Length in a Binary Tree #include using namespace std ; // To represent a node of a Binary Tree struct Node { Node * left * right ; int val ; }; // Create a new Node and return its address Node * newNode ( int val ) { Node * temp = new Node (); temp -> val = val ; temp -> left = temp -> right = NULL ; return temp ; } // Returns the maximum consecutive Path Length int maxPathLenUtil ( Node * root int prev_val int prev_len ) { if ( ! root ) return prev_len ; // Get the value of Current Node // The value of the current node will be // prev Node for its left and right children int cur_val = root -> val ; // If current node has to be a part of the // consecutive path then it should be 1 greater // than the value of the previous node if ( cur_val == prev_val + 1 ) { // a) Find the length of the Left Path // b) Find the length of the Right Path // Return the maximum of Left path and Right path return max ( maxPathLenUtil ( root -> left cur_val prev_len + 1 ) maxPathLenUtil ( root -> right cur_val prev_len + 1 )); } // Find length of the maximum path under subtree rooted with this // node (The path may or may not include this node) int newPathLen = max ( maxPathLenUtil ( root -> left cur_val 1 ) maxPathLenUtil ( root -> right cur_val 1 )); // Take the maximum previous path and path under subtree rooted // with this node. return max ( prev_len newPathLen ); } // A wrapper over maxPathLenUtil(). int maxConsecutivePathLength ( Node * root ) { // Return 0 if root is NULL if ( root == NULL ) return 0 ; // Else compute Maximum Consecutive Increasing Path // Length using maxPathLenUtil. return maxPathLenUtil ( root root -> val -1 0 ); } //Driver program to test above function int main () { Node * root = newNode ( 10 ); root -> left = newNode ( 11 ); root -> right = newNode ( 9 ); root -> left -> left = newNode ( 13 ); root -> left -> right = newNode ( 12 ); root -> right -> left = newNode ( 13 ); root -> right -> right = newNode ( 8 ); cout < < 'Maximum Consecutive Increasing Path Length is ' < < maxConsecutivePathLength ( root ); return 0 ; }
Java // Java Program to find Maximum Consecutive // Path Length in a Binary Tree import java.util.* ; class GfG { // To represent a node of a Binary Tree static class Node { Node left right ; int val ; } // Create a new Node and return its address static Node newNode ( int val ) { Node temp = new Node (); temp . val = val ; temp . left = null ; temp . right = null ; return temp ; } // Returns the maximum consecutive Path Length static int maxPathLenUtil ( Node root int prev_val int prev_len ) { if ( root == null ) return prev_len ; // Get the value of Current Node // The value of the current node will be // prev Node for its left and right children int cur_val = root . val ; // If current node has to be a part of the // consecutive path then it should be 1 greater // than the value of the previous node if ( cur_val == prev_val + 1 ) { // a) Find the length of the Left Path // b) Find the length of the Right Path // Return the maximum of Left path and Right path return Math . max ( maxPathLenUtil ( root . left cur_val prev_len + 1 ) maxPathLenUtil ( root . right cur_val prev_len + 1 )); } // Find length of the maximum path under subtree rooted with this // node (The path may or may not include this node) int newPathLen = Math . max ( maxPathLenUtil ( root . left cur_val 1 ) maxPathLenUtil ( root . right cur_val 1 )); // Take the maximum previous path and path under subtree rooted // with this node. return Math . max ( prev_len newPathLen ); } // A wrapper over maxPathLenUtil(). static int maxConsecutivePathLength ( Node root ) { // Return 0 if root is NULL if ( root == null ) return 0 ; // Else compute Maximum Consecutive Increasing Path // Length using maxPathLenUtil. return maxPathLenUtil ( root root . val - 1 0 ); } //Driver program to test above function public static void main ( String [] args ) { Node root = newNode ( 10 ); root . left = newNode ( 11 ); root . right = newNode ( 9 ); root . left . left = newNode ( 13 ); root . left . right = newNode ( 12 ); root . right . left = newNode ( 13 ); root . right . right = newNode ( 8 ); System . out . println ( 'Maximum Consecutive Increasing Path Length is ' + maxConsecutivePathLength ( root )); } }
Python3 # Python program to find Maximum consecutive # path length in binary tree # A binary tree node class Node : # Constructor to create a new node def __init__ ( self val ): self . val = val self . left = None self . right = None # Returns the maximum consecutive path length def maxPathLenUtil ( root prev_val prev_len ): if root is None : return prev_len # Get the value of current node # The value of the current node will be # prev node for its left and right children curr_val = root . val # If current node has to be a part of the # consecutive path then it should be 1 greater # than the value of the previous node if curr_val == prev_val + 1 : # a) Find the length of the left path # b) Find the length of the right path # Return the maximum of left path and right path return max ( maxPathLenUtil ( root . left curr_val prev_len + 1 ) maxPathLenUtil ( root . right curr_val prev_len + 1 )) # Find the length of the maximum path under subtree # rooted with this node newPathLen = max ( maxPathLenUtil ( root . left curr_val 1 ) maxPathLenUtil ( root . right curr_val 1 )) # Take the maximum previous path and path under subtree # rooted with this node return max ( prev_len newPathLen ) # A Wrapper over maxPathLenUtil() def maxConsecutivePathLength ( root ): # Return 0 if root is None if root is None : return 0 # Else compute maximum consecutive increasing path # length using maxPathLenUtil return maxPathLenUtil ( root root . val - 1 0 ) # Driver program to test above function root = Node ( 10 ) root . left = Node ( 11 ) root . right = Node ( 9 ) root . left . left = Node ( 13 ) root . left . right = Node ( 12 ) root . right . left = Node ( 13 ) root . right . right = Node ( 8 ) print ( 'Maximum Consecutive Increasing Path Length is' ) print ( maxConsecutivePathLength ( root )) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C# // C# Program to find Maximum Consecutive // Path Length in a Binary Tree using System ; class GfG { // To represent a node of a Binary Tree class Node { public Node left right ; public int val ; } // Create a new Node and return its address static Node newNode ( int val ) { Node temp = new Node (); temp . val = val ; temp . left = null ; temp . right = null ; return temp ; } // Returns the maximum consecutive Path Length static int maxPathLenUtil ( Node root int prev_val int prev_len ) { if ( root == null ) return prev_len ; // Get the value of Current Node // The value of the current node will be // prev Node for its left and right children int cur_val = root . val ; // If current node has to be a part of the // consecutive path then it should be 1 greater // than the value of the previous node if ( cur_val == prev_val + 1 ) { // a) Find the length of the Left Path // b) Find the length of the Right Path // Return the maximum of Left path and Right path return Math . Max ( maxPathLenUtil ( root . left cur_val prev_len + 1 ) maxPathLenUtil ( root . right cur_val prev_len + 1 )); } // Find length of the maximum path under subtree rooted with this // node (The path may or may not include this node) int newPathLen = Math . Max ( maxPathLenUtil ( root . left cur_val 1 ) maxPathLenUtil ( root . right cur_val 1 )); // Take the maximum previous path and path under subtree rooted // with this node. return Math . Max ( prev_len newPathLen ); } // A wrapper over maxPathLenUtil(). static int maxConsecutivePathLength ( Node root ) { // Return 0 if root is NULL if ( root == null ) return 0 ; // Else compute Maximum Consecutive Increasing Path // Length using maxPathLenUtil. return maxPathLenUtil ( root root . val - 1 0 ); } // Driver code public static void Main ( String [] args ) { Node root = newNode ( 10 ); root . left = newNode ( 11 ); root . right = newNode ( 9 ); root . left . left = newNode ( 13 ); root . left . right = newNode ( 12 ); root . right . left = newNode ( 13 ); root . right . right = newNode ( 8 ); Console . WriteLine ( 'Maximum Consecutive' + ' Increasing Path Length is ' + maxConsecutivePathLength ( root )); } } // This code has been contributed by 29AjayKumar
JavaScript < script > // Javascript Program to find Maximum Consecutive // Path Length in a Binary Tree // To represent a node of a Binary Tree class Node { constructor ( val ) { this . val = val ; this . left = this . right = null ; } } // Returns the maximum consecutive Path Length function maxPathLenUtil ( root prev_val prev_len ) { if ( root == null ) return prev_len ; // Get the value of Current Node // The value of the current node will be // prev Node for its left and right children let cur_val = root . val ; // If current node has to be a part of the // consecutive path then it should be 1 greater // than the value of the previous node if ( cur_val == prev_val + 1 ) { // a) Find the length of the Left Path // b) Find the length of the Right Path // Return the maximum of Left path and Right path return Math . max ( maxPathLenUtil ( root . left cur_val prev_len + 1 ) maxPathLenUtil ( root . right cur_val prev_len + 1 )); } // Find length of the maximum path under subtree rooted with this // node (The path may or may not include this node) let newPathLen = Math . max ( maxPathLenUtil ( root . left cur_val 1 ) maxPathLenUtil ( root . right cur_val 1 )); // Take the maximum previous path and path under subtree rooted // with this node. return Math . max ( prev_len newPathLen ); } // A wrapper over maxPathLenUtil(). function maxConsecutivePathLength ( root ) { // Return 0 if root is NULL if ( root == null ) return 0 ; // Else compute Maximum Consecutive Increasing Path // Length using maxPathLenUtil. return maxPathLenUtil ( root root . val - 1 0 ); } // Driver program to test above function let root = new Node ( 10 ); root . left = new Node ( 11 ); root . right = new Node ( 9 ); root . left . left = new Node ( 13 ); root . left . right = new Node ( 12 ); root . right . left = new Node ( 13 ); root . right . right = new Node ( 8 ); document . write ( 'Maximum Consecutive Increasing Path Length is ' + maxConsecutivePathLength ( root ) + '
' ); // This code is contributed by rag2127 < /script>
Lähtö
Maximum Consecutive Increasing Path Length is 3
Aika monimutkaisuus: O(n^2) missä n on solmujen lukumäärä tietyssä binääripuussa.
Aputila: O(log(n))
