Le plus grand nombre en BST inférieur ou égal à k
Étant donné la racine d'un Arbre de recherche binaire et un entier k . La tâche est de trouver le le plus grand nombre dans l'arbre de recherche binaire qui est moins que ou égal à k si aucun élément de ce type n'existe, imprimez -1.
Exemples :
Saisir:
Sortir : 21
Explication : 19 et 25 sont les deux nombres les plus proches de 21 et 19 est le plus grand nombre ayant une valeur inférieure ou égale à 21.
Saisir:
Sortir : 3
Explication : 3 et 5 sont les deux nombres les plus proches de 4 et 3 est le plus grand nombre ayant une valeur inférieure ou égale à 4.
Table des matières
- [Approche naïve] Utilisation de la récursion - O(h) Time et O(h) Space
- [Approche attendue] Utilisation de l'itération - O(h) Time et O(1) Space
[Approche naïve] Utilisation de la récursion - O(h) Time et O(h) Space
C++L'idée est de commencer par racine et comparez sa valeur avec k. Si la valeur du nœud est supérieure à k, déplacez-vous vers le sous-arbre de gauche. Sinon, trouvez la valeur du plus grand nombre inférieur à k dans le sous-arbre droit . Si le sous-arbre droit renvoie -1 (ce qui signifie qu'aucune valeur de ce type n'existe), renvoie la valeur du nœud actuel. Sinon, renvoie la valeur renvoyée par le sous-arbre droit (car elle sera supérieure à la valeur du nœud actuel mais inférieure à 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 ));
Sortir
21
[Approche attendue] Utilisation de l'itération - O(h) Time et O(1) Space
C++L'idée est de commencer par racine et comparer sa valeur avec k . Si la valeur du nœud est <= k mettre à jour la valeur du résultat avec la valeur de root et passer au droite sous-arbre, sinon déplacez-vous vers le gauche sous-arbre. Par de manière itérative en appliquant cette opération sur tous les nœuds, nous pouvons minimiser l'espace nécessaire pour le récursivité empiler.
// 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 ));
Sortir
21Créer un quiz
