ກວດເບິ່ງວ່າອາເລທີ່ ກຳ ນົດໃຫ້ສາມາດເປັນຕົວແທນຂອງ Preorder Traversal of Binary Search Tree


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon LinkedIn
ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ Stack ຕົ້ນໄມ້

ບັນຫາ“ ກວດເບິ່ງວ່າແຖວໃດ ໜຶ່ງ ທີ່ສາມາດເປັນຕົວແທນຂອງ Preorder Traversal of Binary Search Tree” ລະບຸວ່າທ່ານຖືກກ preversvers ຜ່ານ ລໍາດັບ. ຕອນນີ້ພິຈາລະນາລໍາດັບນີ້ແລະຊອກຫາວ່າລໍາດັບນີ້ສາມາດເປັນຕົວແທນຂອງຕົ້ນໄມ້ຄົ້ນຫາຖານສອງຫຼືບໍ່? ຄວາມສັບສົນທີ່ໃຊ້ເວລາທີ່ຄາດໄວ້ ສຳ ລັບການແກ້ໄຂແມ່ນ O (1).

ຍົກຕົວຢ່າງ

ກວດເບິ່ງວ່າອາເລທີ່ ກຳ ນົດໃຫ້ສາມາດເປັນຕົວແທນຂອງ Preorder Traversal of Binary Search Tree

5 3 4 7 6 9 8 11
Yes

ວິທີການເພື່ອກວດກາເບິ່ງວ່າ ລຳ ດັບຄວາມຕ້ອງການທີ່ເປັນຕົວແທນ BST

ບັນຫາຂໍໃຫ້ພວກເຮົາກວດເບິ່ງວ່າອາເລທີ່ມອບໃຫ້ສາມາດເປັນຕົວແທນຂອງ Preorder Traversal of the ຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ. ພວກເຮົາໄດ້ຮັບ integer array ເປັນວັດສະດຸປ້ອນ. ຕອນນີ້ພິຈາລະນາວ່າອາເລນີ້ມີ preversvers ຜ່ານ ລໍາດັບສໍາລັບຕົ້ນໄມ້ຄົ້ນຫາຖານສອງ. ຫຼັງຈາກນັ້ນໃຫ້ກວດເບິ່ງວ່າ ລຳ ດັບການ ລຳ ດັບ preorder ທີ່ໃຫ້ໄວ້ແມ່ນສາມາດເປັນຕົວແທນຂອງຕົ້ນໄມ້ການຄົ້ນຫາຖານສອງຫລືບໍ່.

ວິທີການທີ່ໂງ່ຈ້າແມ່ນການຊອກຫາອົງປະກອບທີ່ໃຫຍ່ກວ່າໃນປັດຈຸບັນທີ່ຢູ່ເບື້ອງຂວາຂອງມັນ. ຕອນນີ້ກວດເບິ່ງວ່າທຸກໆອົງປະກອບທີ່ຢູ່ເບື້ອງຂວາຂອງມັນຈະໃຫຍ່ກວ່າອົງປະກອບປັດຈຸບັນທີ່ຖືກເລືອກໄວ້. ແລະທຸກໆອົງປະກອບທີ່ຢູ່ເບື້ອງຊ້າຍຂອງອົງປະກອບທີ່ໃຫຍ່ກວ່າແລະອົງປະກອບປັດຈຸບັນທີ່ຖືກເລືອກແມ່ນນ້ອຍກວ່າມັນ. ຫຼັງຈາກນັ້ນກວດເບິ່ງສະພາບການດຽວກັນ ສຳ ລັບເສັ້ນເລືອດຂອດຊ້າຍຈາກປັດຈຸບັນໄປຫາອົງປະກອບນ້ອຍກວ່າອົງປະກອບທີ່ໃຫຍ່ກວ່າ. ແລະຍັງ ຕາມການນັດພົບ ກວດເບິ່ງ subarray ຈາກອົງປະກອບທີ່ໃຫຍ່ກວ່າຈົນເຖິງທີ່ສຸດ. ວິທີການນີ້ບໍ່ມີປະສິດທິພາບເພາະວ່ານີ້ຕ້ອງໃຊ້ເວລາສັບສົນ O (N ^ 2).

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

ລະຫັດ

ລະຫັດ C ++ ເພື່ອກວດເບິ່ງວ່າອາເລທີ່ໃຫ້ຢູ່ສາມາດເປັນຕົວແທນການລ້າໆຂອງ BST

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

bool preorderBST(int input[], int n)
{
    stack<int> s;
    int root = INT_MIN;
    for(int i=0;i<n;i++)
    {
        // if current node is smaller than the root
        // the current node lies on the right of root
        // thus it is impossible for bst
        if (input[i] < root)
            return false;
        // keep removing elements smaller than the root
        // until you find an element which is greater than the root
        while(!s.empty() && s.top()<input[i])
            root = s.top(), s.pop();
        // if current element is smaller than the root
        // push it into stack
        s.push(input[i]);
    }
    // if we passed until the end of the array
    // that means that the given preorder sequence represents a valid BST
    return true;
}

int main()
{
    int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
    int n = (sizeof input)/(sizeof input[0]);

    cout<<((preorderBST(input, n)) ? "yes" : "no");
}
yes

ລະຫັດ Java ເພື່ອກວດສອບວ່າອາເລທີ່ໃຫ້ສາມາດເປັນຕົວແທນຂອງການປ່ຽນເສັ້ນທາງຂອງ BST ໄດ້

import java.util.*;

class Main{
  static boolean preorderBST(int input[], int n)
  {
      Stack<Integer> s = new Stack<Integer>();
      int root = Integer.MIN_VALUE;
      for(int i=0;i<n;i++)
      {
          // if current node is smaller than the root
          // the current node lies on the right of root
          // thus it is impossible for bst
          if (input[i] < root)
              return false;
          // keep removing elements smaller than the root
          // until you find an element which is greater than the root
          while(!s.empty() && s.peek()<input[i]){
              root = s.peek();
              s.pop();
          }
          // if current element is smaller than the root
          // push it into stack
          s.push(input[i]);
      }
      // if we passed until the end of the array
      // that means that the given preorder sequence represents a valid BST
      return true;
  }

  public static void main(String[] args)
  {
      int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
      int n = input.length;

      System.out.print((preorderBST(input, n)) ? "yes" : "no");
  }
}
yes

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

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

ໂອ (N), ນັບຕັ້ງແຕ່ພວກເຮົາໄດ້ຜ່ານການດັດສະນີທັງ ໝົດ ໃນເຄື່ອງປ້ອນຂໍ້ມູນໃຫ້. ດັ່ງນັ້ນຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

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

ໂອ (N), ເພາະວ່າພວກເຮົາໄດ້ໃຊ້ຂັ້ນໄດ. ດັ່ງນັ້ນໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດ, ພວກເຮົາສາມາດຈົບການເກັບມ້ຽນທັງ ໝົດ.