logo

TechCodeview

Største tall i BST som er mindre enn eller lik k

Gitt roten til en Binært søketre og et heltall k . Oppgaven er å finne største antall i det binære søketreet altså mindre enn eller lik til k hvis det ikke finnes noe slikt element skriv ut -1. 

Eksempler:  

Inndata:



Største-antall-i-BST-som-er-mindre-enn-eller-lik-k-1' title=

Utgang: 21
Forklaring: 19 og 25 er de to tallene som er nærmest 21, og 19 er det største tallet med verdi mindre enn eller lik 21.

Inndata:

Største-antall-i-BST-som-er-mindre-enn-eller-lik-til-k-2' loading='lazy' title=

Utgang: 3
Forklaring: 3 og 5 er de to tallene som er nærmest 4, og 3 er det største tallet med verdi mindre enn eller lik 4.

Innholdsfortegnelse

[Naiv tilnærming] Bruke rekursjon - O(h) Tid og O(h) Space

Tanken er å begynne på rot og sammenlign verdien med k. Hvis nodens verdi er større enn k, flytt til venstre undertre. Ellers finn verdien av største tall mindre enn lik k i høyre undertre . Hvis høyre undertre returnerer -1 (som betyr at ingen slik verdi eksisterer), så returner gjeldende nodes verdi. Ellers returnerer verdien returnert av høyre undertre (da den vil være større enn gjeldende nodes verdi, men mindre enn lik 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));

Produksjon 
21

[Forventet tilnærming] Bruke iterasjon - O(h) Tid og O(1) Mellomrom

Tanken er å begynne på rot og sammenligne dens verdi med k . Hvis nodens verdi er <= k oppdater resultatverdien til roots verdi og flytt til høyre undertre ellers flytte til Igjen undertre. Ved iterativt Ved å bruke denne operasjonen på tvers av alle noder kan vi minimere plassen som trengs for rekursjon stable.

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));

Produksjon 
21
Lag quiz