BST Leetcode Həllində K-ci Ən Kiçik Element

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

BST Leetcode Həllində K-ci Ən Kiçik Element – ​​Nəzərə alınmaqla root ikili axtarış ağacı və tam ədəd k, qayıt bu k^th ən kiçik dəyər (1 indeksli) ağacdakı qovşaqların bütün dəyərlərindən.

Nümunələr:

Pin

Input:

 root = [3,1,4,null,2], k = 1

Çıxış:

 1

 

Pin

Input:

 root = [5,3,6,2,4,null,null,1], k = 3

Çıxış:

 3

Explanation:

Verilmiş BST-də 3-cü ən kiçik ədəd 3-dür, ona görə də 3-ü çıxarırıq.

Yanaşma

• İkili ağac sıralanmış qaydada elementlərdən ibarətdir.
• Həlli tapmağın ən asan yolu elementləri prioritet növbəyə daxil etmək və sonra k-1 elementlərini çıxarmaqdır, sonra prioritet növbənin yuxarı elementi ağacın k-ci ən kiçik elementidir.
• Optimallaşdırılmış həll sıra ilə keçid edir və ziyarət edilən elementlərin sayının hesabını aparır.
•  İkili ağacın ən sol elementini ziyarət etdikdən sonra, saymanı 1-ə qədər artırın və ardıcıllıqla geri dönün və sayı artırın.
• Say k-yə çatdıqda həmin elementi qaytarın.

Idea:

Fikir BST-dən keçin nizam moda, BST-nin sıra keçidi artan ardıcıllıqla sıralandığı üçün biz edə bilərik hər dəfə bu say k-yə bərabər olduqda, bir hesab saxlamaq, biz K-ci ən kiçik elementimizi tapdıq, ona görə də onu qaytarırıq.

BST-ni sıradan bir keçidlə keçmək üçün, yığından istifadə edə bilərik. Əvvəlcə hər bir nodu yığına daxil edərək ən soldakı qovşaqdan keçirik ki, biz null tapana qədər, sonra yığından elementləri bir-bir çıxarırıq və həmin qovşağın sağına keçirik.

BST-də K-ci Ən Kiçik Element üçün Kod

C ++ kodu

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        
        stack<TreeNode*> st;
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=NULL){
                st.push(root);
                root = root->left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.top();
            st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root->val;
            }
            
            root = root->right;
            //move to the next largest node which is at the right in BST.
        }
        
    }
};

Java kodu

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        LinkedList<TreeNode> st = new LinkedList<>();
        // stack to store the node pointers.
        
        while(true){
            
            while(root!=null){
                st.push(root);
                root = root.left;
            }
            // traversing to the leftmost of a node and inserting it into stack.
            root = st.pop();
            k--;
            if(k==0){
                // if its Kth smallest then return it.
                return root.val;
            }
            
            root = root.right;
            //move to the next largest node which is at the right in BST.
        }
    }
}

BST Leetcode Həllində K-ci Ən Kiçik Element üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Zaman mürəkkəbliyi O(H+k), burada H ağacın hündürlüyüdür, çünki yığından elementləri çıxarmazdan əvvəl yarpaq düyününə gedirik və sonra elementləri açmağa başlayırıq, buna görə də ümumi vaxt mürəkkəbliyi O(logn) yarpaq düyününə qədər getmək üçün, və əlavə O(k) K-ci ən kiçik elementi tapmaq vaxtı. Ümumi zaman mürəkkəbliyi O (logn + k) üçün balanslı ağac və O(N + k) üçün bu Əyilmiş ağac.

Kosmik Mürəkkəblik

Biz xarici məkandan istifadə edirik, yəni qalaq, istənilən vaxt ağacın hündürlüyündən çox elementlərin sayı olmayacaq, Beləliklə, ümumi fəzanın mürəkkəbliyi O(H).