ໂປຣແກຣມກວດສອບວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫຼືບໍ່  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Adobe Amazon Boomerang ການຄ້າ ປັດໃຈ ສີເທົາສີສົ້ມ MakeMyTrip Microsoft Oracle ຫ້ອງ OYO Qualcomm Snapdeal VMware ຫ້ອງທົດລອງ Walmart Wooker
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ ຕົ້ນໄມ້ຖານສອງ ຕົ້ນໄມ້

ຖະແຫຼງການບັນຫາ  

“ ໂປແກຼມກວດສອບວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫລືບໍ່” ກ່າວວ່າທ່ານໄດ້ຮັບຕົ້ນໄມ້ໄບນາລີແລະທ່ານຕ້ອງກວດເບິ່ງວ່າຕົ້ນໄມ້ຖານສອງຕອບສະ ໜອງ ຄຸນສົມບັດຂອງຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ. ສະນັ້ນ, ຕົ້ນໄມ້ໄບນາລີມີຄຸນສົມບັດດັ່ງຕໍ່ໄປນີ້: 

  1. ລັດຖະບັນຍັດດ້ານຊ້າຍຄວນມີຂໍ້ທີ່ມີຄ່າຕ່ ຳ ກວ່າຮາກ
  2. ລັດຖະບັນຍັດທີ່ຖືກຕ້ອງຄວນມີຂໍ້ທີ່ມີຂໍ້ມູນຫຼາຍກ່ວາຮາກ
  3. ລັດຖະບັນຍັດເບື້ອງຊ້າຍແລະຂວາຄວນຈະເປັນຕົ້ນໄມ້ຄົ້ນຫາຖານສອງເຊິ່ງ ໝາຍ ຄວາມວ່າພວກເຂົາເອງຄວນຈະປະຕິບັດຕາມຄຸນສົມບັດຂອງຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ

ໂປຣແກຣມກວດສອບວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫຼືບໍ່Pin

YES

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

ການປ້ອນຂໍ້ມູນ

Pin

NO

ຄຳ ອະທິບາຍ: ຕົ້ນໄມ້ບໍ່ປະຕິບັດຕາມຄຸນສົມບັດຂອງ BST, ບ່ອນທີ່ຂໍ້ທັງ ໝົດ ໃນບົດບັນຍັດເບື້ອງຊ້າຍຄວນມີຄ່ານ້ອຍກວ່າຮາກ.

ເຂົ້າຫາໂປແກຼມເພື່ອກວດເບິ່ງວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫຼືບໍ່  

ວິທີການ Naive (ວິທີການທີ່ບໍ່ຖືກຕ້ອງ)

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

ດໍາເນີນການຄິດໄລ່ກ່ຽວກັບຕົ້ນໄມ້ທີ່ໃຫ້ (ຮູບພາບ). ທ່ານຈະພົບວ່າເຖິງແມ່ນວ່າສູດການຄິດໄລ່ຈະກັບຄືນວ່າຕົ້ນໄມ້ຖານສອງທີ່ຖືກມອບໃຫ້ແມ່ນ BST. ແຕ່ຍ້ອນວ່າ 1 ໃນລັດຖະບັນຍັດທີ່ຖືກຕ້ອງແມ່ນນ້ອຍກວ່າ 2. ສະນັ້ນ, ພວກເຮົາຕ້ອງຊອກຫາບາງວິທີການອື່ນ.

ວິທີການທີ່ມີປະສິດຕິພາບ (ວິທີການທີ່ຖືກຕ້ອງ)

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

ລະຫັດ  

ໂປຣແກຣມ C ++ ເພື່ອກວດເບິ່ງວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫຼືບໍ່

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
} ;

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}

bool isThisBST(node* root, int minimum, int maximum)
{
    // if there is no tree
    if(!root)
        return true;

    // the root should be in the range defined by [minimum, maximum]
    if(root->data < minimum || root->data > maximum)
        return false;
    // if the root satisfies the value then we recursively check the same for left and right subtree
    // we set the minimum and maximum for left and right subtrees accordingly.
    return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}

int main()
{
    node *root = create(2);
    root->left = create(1);
    root->right = create(4);
    root->right->left = create(3);
    root->right->right = create(5);

    bool isBST = isThisBST(root, INT_MIN, INT_MAX);
    cout<<((isBST == true) ? "YES" : "NO");
    return 0;
}
YES

Java program ເພື່ອກວດເບິ່ງວ່າຕົ້ນໄມ້ຖານສອງແມ່ນ BST ຫລືບໍ່

// Class that denote a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
} 

class Tree 
{ 
    static Node root; 
  
  // return true if the tree is BST else return false
    static boolean isThisBST(Node root, int minimum, int maximum)
    { 
        // if there is no tree
      if(root == null)
          return true;
  
      // the root should be in the range defined by [minimum, maximum]
      if(root.data < minimum || root.data > maximum)
          return false;
      // if the root satisfies the value then we recursively check the same for left and right subtree
      // we set the minimum and maximum for left and right subtrees accordingly.
      return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new Node(2); 
        tree.root.left = new Node(1); 
        tree.root.right = new Node(4); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(5); 
  
        boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    	System.out.print((isBST == true) ? "YES" : "NO");
    }
}
YES

ການວິເຄາະຄວາມສັບສົນ  

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

ໂອ (N), ເພາະວ່າພວກເຮົາເດີນຜ່ານຕົ້ນໄມ້ເທົ່ານັ້ນ. ແລະຄ່າຜ່ານທາງດຽວແມ່ນຄ່າໃຊ້ຈ່າຍສັບສົນທີ່ໃຊ້ເວລາ.

ເບິ່ງ
ການແກ້ໄຂໄລຍະໄກ Leetcode

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

O (1) ພື້ນທີ່ຄົງທີ່ເພາະວ່າພວກເຮົາໃຊ້ພຽງແຕ່ ຈຳ ນວນຕົວແປທີ່ຄົງທີ່ເທົ່ານັ້ນແຕ່ໂປແກມທັງ ໝົດ ຈະໃຊ້ O (N) ເພາະວ່າມີ N Nodes ຢູ່ໃນຕົ້ນໄມ້.