Största nummer i BST som är mindre än eller lika med k
Med tanke på roten till en Binärt sökträd och ett heltal k . Uppgiften är att hitta största antal i det binära sökträdet alltså mindre än eller lika till k om inget sådant element finns skriv ut -1.
Exempel:
Input:
Utgång: 21
Förklaring: 19 och 25 är två siffror som ligger närmast 21 och 19 är det största talet som har ett värde mindre än eller lika med 21.
Input:
Utgång: 3
3 & 5 är två närmast 4 och 3 är det största talet som har ett värde mindre än eller lika med 4.
Innehållsförteckning
- [Naiv metod] Använda rekursion - O(h) Tid och O(h) Mellanrum
- [Förväntad tillvägagångssätt] Använder iteration - O(h) Tid och O(1) Mellanrum
[Naiv metod] Använda rekursion - O(h) Tid och O(h) Mellanrum
C++Tanken är att börja på rot och jämför dess värde med k. Om nodens värde är större än k, flytta till det vänstra underträdet. Annars hitta värdet av största antal mindre än lika med k i höger underträd . Om höger underträd returnerar -1 (vilket betyder att inget sådant värde existerar) returnerar du den aktuella nodens värde. Annars returneras värdet som returneras av höger underträd (eftersom det kommer att vara större än den nuvarande nodens värde men mindre än lika med k).
// C++ code to find the largest value // smaller than or equal to k using recursion #include using namespace std ; class Node { public : int data ; Node * left * right ; Node ( int val ){ data = val ; left = nullptr ; right = nullptr ; } }; // function to find max value less than k int findMaxFork ( Node * root int k ) { // Base cases if ( root == nullptr ) return -1 ; if ( root -> data == k ) return k ; // If root's value is smaller // try in right subtree else if ( root -> data < k ) { int x = findMaxFork ( root -> right k ); if ( x == -1 ) return root -> data ; else return x ; } // If root's data is greater // return value from left subtree. return findMaxFork ( root -> left k ); } int main () { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node * root = new Node ( 5 ); root -> left = new Node ( 2 ); root -> left -> left = new Node ( 1 ); root -> left -> right = new Node ( 3 ); root -> right = new Node ( 12 ); root -> right -> left = new Node ( 9 ); root -> right -> right = new Node ( 21 ); root -> right -> right -> left = new Node ( 19 ); root -> right -> right -> right = new Node ( 25 ); cout < < findMaxFork ( root k ); return 0 ; }
Java // Java code to find the largest value // smaller than or equal to k using recursion class Node { int data ; Node left right ; Node ( int val ) { data = val ; left = null ; right = null ; } } class GfG { // function to find max value less than k static int findMaxFork ( Node root int k ) { // Base cases if ( root == null ) return - 1 ; if ( root . data == k ) return k ; // If root's value is smaller // try in right subtree else if ( root . data < k ) { int x = findMaxFork ( root . right k ); if ( x == - 1 ) return root . data ; else return x ; } // If root's data is greater // return value from left subtree. return findMaxFork ( root . left k ); } public static void main ( String [] args ) { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); System . out . println ( findMaxFork ( root k )); } }
Python # Python code to find the largest value # smaller than or equal to k using recursion class Node : def __init__ ( self val ): self . data = val self . left = None self . right = None # function to find max value less than k def findMaxFork ( root k ): # Base cases if root is None : return - 1 if root . data == k : return k # If root's value is smaller # try in right subtree elif root . data < k : x = findMaxFork ( root . right k ) if x == - 1 : return root . data else : return x # If root's data is greater # return value from left subtree. return findMaxFork ( root . left k ) if __name__ == '__main__' : k = 24 # creating following BST # # 5 # / # 2 12 # / / # 1 3 9 21 # / # 19 25 root = Node ( 5 ) root . left = Node ( 2 ) root . left . left = Node ( 1 ) root . left . right = Node ( 3 ) root . right = Node ( 12 ) root . right . left = Node ( 9 ) root . right . right = Node ( 21 ) root . right . right . left = Node ( 19 ) root . right . right . right = Node ( 25 ) print ( findMaxFork ( root k ))
C# // C# code to find the largest value // smaller than or equal to k using recursion using System ; class Node { public int data ; public Node left right ; public Node ( int val ) { data = val ; left = null ; right = null ; } } class GfG { // function to find max value less than k static int FindMaxFork ( Node root int k ) { // Base cases if ( root == null ) return - 1 ; if ( root . data == k ) return k ; // If root's value is smaller // try in right subtree else if ( root . data < k ) { int x = FindMaxFork ( root . right k ); if ( x == - 1 ) return root . data ; else return x ; } // If root's data is greater // return value from left subtree. return FindMaxFork ( root . left k ); } static void Main () { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); Console . WriteLine ( FindMaxFork ( root k )); } }
JavaScript // JavaScript code to find the largest value // smaller than or equal to k using recursion class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } // function to find max value less than k function findMaxFork ( root k ) { // Base cases if ( root === null ) return - 1 ; if ( root . data === k ) return k ; // If root's value is smaller // try in right subtree else if ( root . data < k ) { let x = findMaxFork ( root . right k ); if ( x === - 1 ) return root . data ; else return x ; } // If root's data is greater // return value from left subtree. return findMaxFork ( root . left k ); } let k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 let root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); console . log ( findMaxFork ( root k ));
Produktion
21
[Förväntad tillvägagångssätt] Använder iteration - O(h) Tid och O(1) Mellanrum
C++Tanken är att börja på rot och jämför dess värde med k . Om nodens värde är <= k uppdatera resultatvärdet till roots värde och flytta till rätt underträd annars flytta till vänster underträd. Av iterativt Genom att tillämpa denna operation över alla noder kan vi minimera det utrymme som behövs för rekursion stack.
// C++ code to find the largest value // smaller than or equal to k using recursion #include using namespace std ; class Node { public : int data ; Node * left * right ; Node ( int val ){ data = val ; left = nullptr ; right = nullptr ; } }; // function to find max value less than k int findMaxFork ( Node * root int k ) { int result = -1 ; // Start from root and keep looking for larger while ( root != nullptr ) { // If root is smaller go to right side if ( root -> data <= k ){ result = root -> data ; root = root -> right ; } // If root is greater go to left side else root = root -> left ; } return result ; } int main () { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node * root = new Node ( 5 ); root -> left = new Node ( 2 ); root -> left -> left = new Node ( 1 ); root -> left -> right = new Node ( 3 ); root -> right = new Node ( 12 ); root -> right -> left = new Node ( 9 ); root -> right -> right = new Node ( 21 ); root -> right -> right -> left = new Node ( 19 ); root -> right -> right -> right = new Node ( 25 ); cout < < findMaxFork ( root k ); return 0 ; }
Java // Java code to find the largest value // smaller than or equal to k using recursion class Node { int data ; Node left right ; Node ( int val ) { data = val ; left = null ; right = null ; } } class GfG { // function to find max value less than k static int findMaxFork ( Node root int k ) { int result = - 1 ; // Start from root and keep looking for larger while ( root != null ) { // If root is smaller go to right side if ( root . data <= k ) { result = root . data ; root = root . right ; } // If root is greater go to left side else { root = root . left ; } } return result ; } public static void main ( String [] args ) { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); System . out . println ( findMaxFork ( root k )); } }
Python # Python code to find the largest value # smaller than or equal to k using recursion class Node : def __init__ ( self val ): self . data = val self . left = None self . right = None # function to find max value less than k def findMaxFork ( root k ): result = - 1 # Start from root and keep looking for larger while root is not None : # If root is smaller go to right side if root . data <= k : result = root . data root = root . right # If root is greater go to left side else : root = root . left return result if __name__ == '__main__' : k = 24 # creating following BST # # 5 # / # 2 12 # / / # 1 3 9 21 # / # 19 25 root = Node ( 5 ) root . left = Node ( 2 ) root . left . left = Node ( 1 ) root . left . right = Node ( 3 ) root . right = Node ( 12 ) root . right . left = Node ( 9 ) root . right . right = Node ( 21 ) root . right . right . left = Node ( 19 ) root . right . right . right = Node ( 25 ) print ( findMaxFork ( root k ))
C# // C# code to find the largest value // smaller than or equal to k using recursion using System ; class Node { public int data ; public Node left right ; public Node ( int val ) { data = val ; left = null ; right = null ; } } class GfG { // function to find max value less than k static int FindMaxFork ( Node root int k ) { int result = - 1 ; // Start from root and keep looking for larger while ( root != null ) { // If root is smaller go to right side if ( root . data <= k ) { result = root . data ; root = root . right ; } // If root is greater go to left side else { root = root . left ; } } return result ; } static void Main () { int k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 Node root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); Console . WriteLine ( FindMaxFork ( root k )); } }
JavaScript // JavaScript code to find the largest value // smaller than or equal to k using recursion class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } // function to find max value less than k function findMaxFork ( root k ) { let result = - 1 ; // Start from root and keep looking for larger while ( root !== null ) { // If root is smaller go to right side if ( root . data <= k ) { result = root . data ; root = root . right ; } // If root is greater go to left side else { root = root . left ; } } return result ; } let k = 24 ; // creating following BST // // 5 // / // 2 12 // / / // 1 3 9 21 // / // 19 25 let root = new Node ( 5 ); root . left = new Node ( 2 ); root . left . left = new Node ( 1 ); root . left . right = new Node ( 3 ); root . right = new Node ( 12 ); root . right . left = new Node ( 9 ); root . right . right = new Node ( 21 ); root . right . right . left = new Node ( 19 ); root . right . right . right = new Node ( 25 ); console . log ( findMaxFork ( root k ));
Produktion
21Skapa frågesport
