logo

TechCodeview

Lielākais skaitlis BST, kas ir mazāks par k vai vienāds ar to

Ņemot vērā a sakni Binārais meklēšanas koks un vesels skaitlis k . Uzdevums ir atrast lielākais skaitlis binārajā meklēšanas kokā, kas ir mazāk nekā vai vienāds uz k, ja šāda elementa nav, izdrukā -1. 

Piemēri:  

Ievade:



Lielākais-skaitlis-BST-kas-ir-mazāks-par-vai-vienāds-k-1' title=

Izvade: 21
Paskaidrojums: 19 un 25 ir divi tuvākie skaitļi 21, un 19 ir lielākais skaitlis, kura vērtība ir mazāka vai vienāda ar 21.

Ievade:

Lielākais-skaitlis-BST-kas-mazāks-par-vai-vienāds-k-2' loading='lazy' title=

Izvade: 3
Paskaidrojums: 3 un 5 ir divi tuvākie skaitļi 4, un 3 ir lielākais skaitlis, kura vērtība ir mazāka vai vienāda ar 4.

Satura rādītājs

[Naīvā pieeja] Rekursijas izmantošana - O(h) laiks un O(h) telpa

Ideja ir sākt ar sakne un salīdziniet tā vērtību ar k. Ja mezgla vērtība ir lielāka par k, pārejiet uz kreiso apakškoku. Pretējā gadījumā atrodiet lielākā skaitļa vērtību, kas ir mazāka par vienādu ar k labais apakškoks . Ja labais apakškoks atgriež -1 (tas nozīmē, ka šādas vērtības nav), tad atgriež pašreizējā mezgla vērtību. Pretējā gadījumā tiek atgriezta labā apakškoka atgrieztā vērtība (jo tā būs lielāka par pašreizējā mezgla vērtību, bet mazāka par k).

C++ 
// 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));

Izvade 
21

[Paredzamā pieeja], izmantojot iterāciju – O(h) laiks un O(1) telpa

Ideja ir sākt ar sakne un salīdziniet tā vērtību ar k . Ja mezgla vērtība ir <= k atjauniniet rezultāta vērtību uz saknes vērtību un pārejiet uz pareizi apakškoks cits pārvietot uz pa kreisi apakškoks. Autors iteratīvi piemērojot šo darbību visos mezglos, mēs varam samazināt nepieciešamo vietu rekursija kaudze.

C++ 
// 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));

Izvade 
21
Izveidojiet viktorīnu