Nombre més gran de BST que és menor o igual que k
Donada l'arrel d'a Arbre de cerca binari i un nombre enter k . La tasca és trobar el nombre més gran a l'arbre de cerca binari, és a dir o igual a k si no existeix aquest element imprimiu -1.
Exemples:
Entrada:
Sortida: 21
Explicació: 19 i 25 són els dos nombres més propers a 21 i 19 és el nombre més gran que té un valor inferior o igual a 21.
Entrada:
Sortida: 3
Explicació: 3 i 5 són els dos nombres més propers a 4 i 3 és el nombre més gran que té un valor inferior o igual a 4.
Taula de continguts
- [Enfocament ingenu] Ús de la recursència: O(h) Temps i O(h) Espai
- [Enfocament esperat] Ús de la iteració - O(h) Temps i O(1) Espai
C++La idea és començar pel arrel i compareu el seu valor amb k. Si el valor del node és superior a k, moveu-vos al subarbre esquerre. En cas contrari, trobeu el valor del nombre més gran menor que igual a k en el subarbre dret . Si el subarbre dret retorna -1 (és a dir, no existeix aquest valor), retorna el valor del node actual. En cas contrari, retorna el valor retornat pel subarbre dret (ja que serà més gran que el valor del node actual però menor que igual a 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 ));
Sortida
21
[Enfocament esperat] Ús de la iteració - O(h) Temps i O(1) Espai
C++La idea és començar pel arrel i comparar el seu valor amb k . Si el valor del node és <= k actualitzeu el valor del resultat al valor de l'arrel i aneu a dret subarbre sinó moure's al esquerra subarbre. Per iterativament aplicant aquesta operació a tots els nodes podem minimitzar l'espai necessari per al recursivitat pila.
// 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 ));
Sortida
21Crea un qüestionari
