ຢືນຢັນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ asana Atlassian Bloomberg ByteDance Citadel ເຟສບຸກ Microsoft Oracle Qualtrics VMware Yahoo
ການຄົ້ນຫາຄວາມເລິກຄັ້ງ ທຳ ອິດ Recursion ຕົ້ນໄມ້

ບັນຫາ

In ຢືນຢັນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ບັນຫາທີ່ພວກເຮົາໃຫ້ຮາກຖານຂອງ a ເປັນໄມ້ຢືນຕົ້ນ, ພວກເຮົາຕ້ອງກວດເບິ່ງວ່າມັນແມ່ນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງຫລືບໍ່.

ຕົວຢ່າງ:

ຢືນຢັນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ

ຜົນໄດ້ຮັບ:

ທີ່ແທ້ຈິງ

ຄໍາອະທິບາຍ: ຕົ້ນໄມ້ທີ່ໃຫ້ມານັ້ນແມ່ນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງເພາະວ່າທຸກໆສ່ວນທີ່ປະໄວ້ໃນແຕ່ລະລັດຖະບັນຍັດແມ່ນນ້ອຍກ່ວາຮາກຂອງລັດຖະບັນຍັດ. ທຸກໆອົງປະກອບທີ່ ເໝາະ ສົມກັບແຕ່ລະລັດຖະບັນຍັດແມ່ນໃຫຍ່ກວ່າຮາກຂອງລັດຖະບັນຍັດແລະແຕ່ລະລັດຖະບັນຍັດແມ່ນຕົວຂອງມັນເອງເປັນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ.

ວິທີການ

  • ຫນ້າທໍາອິດ, ພວກເຮົາເຮັດອິນເຕີເນັດ ທາງຜ່ານ ຂອງຕົ້ນໄມ້ທີ່ໄດ້ຮັບແລະເກັບຮັກສາມັນຢູ່ໃນ array. ຫຼັງຈາກນັ້ນ, ພວກເຮົາກວດເບິ່ງວ່າອາເລຖືກຈັດລຽງຕາມ ລຳ ດັບທີ່ເພີ່ມຂື້ນ. ຫຼັງຈາກນັ້ນພວກເຮົາເວົ້າວ່າມັນແມ່ນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງມັນບໍ່ແມ່ນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ.
  • ເພື່ອຫຼຸດຜ່ອນການໃຊ້ພື້ນທີ່ຊ່ວຍ ໜ້ອຍ ທີ່ສຸດພວກເຮົາສາມາດຕິດຕາມ node ທີ່ໄດ້ໄປຢ້ຽມຢາມກ່ອນ ໜ້າ ນີ້ແລະຖ້າ node ປັດຈຸບັນນ້ອຍກວ່າ node ທີ່ຜ່ານມາແລ້ວມັນກໍ່ບໍ່ແມ່ນ ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ແລະຖ້າຂໍ້ທັງ ໝົດ ທີ່ຜ່ານມາມີຂະ ໜາດ ນ້ອຍກວ່າ node ປັດຈຸບັນມັນຈະເປັນໄມ້ຢືນຕົ້ນຄົ້ນຫາຖານສອງ.
  • ພວກເຮົາສາມາດຫລີກລ້ຽງການ ນຳ ໃຊ້ພື້ນທີ່ພິເສດໂດຍການຜ່ານ node ທີ່ຜ່ານມາເປັນພາລາມິເຕີ.

ລະຫັດ C ++ ສຳ ລັບຕົ້ນໄມ້ຄົ້ນຫາທີ່ມີຄວາມຖືກຕ້ອງຂອງຖານສອງ

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(3); 
  root->left	 = new Node(2); 
  root->right	 = new Node(5); 
  root->left->left = new Node(1); 
  root->left->right = new Node(4); 

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
} 

ລະຫັດ Java ສຳ ລັບຕົ້ນໄມ້ຄົ້ນຫາທີ່ມີຄວາມຖືກຕ້ອງຂອງຖານສອງ

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
} 
Not a BST

ຄວາມສັບສົນເວລາ

O (n) ດັ່ງທີ່ພວກເຮົາ ກຳ ລັງຜ່ານແຕ່ລະ node ພຽງແຕ່ຄັ້ງດຽວ.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງເກັບຂໍ້ມູນແຕ່ລະ node ທີ່ຜ່ານການເດີນທາງແລະກວດເບິ່ງວ່າແຖວນັ້ນຖືກຈັດຮຽງຕາມ ລຳ ດັບທີ່ເພີ່ມຂື້ນເພື່ອກວດເບິ່ງວ່າຕົ້ນໄມ້ແມ່ນ Binary Search Tree ຫລືບໍ່.

ເອກະສານ