İkili Axtarış Ağacı Leetcode Həllini bərpa edin

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

The İkili Axtarış Ağacı LeetCode Həllini bərpa edin - "İkili Axtarış Ağacını Bərpa et" bildirir ki, ikili axtarış ağacının kökü verilir, burada dəqiq iki qovşağın dəyərləri səhvən dəyişdirilir. Biz ağacın strukturunu dəyişmədən bərpa etməliyik.

Misal:

Input:  root = [1,3,null,null,2]

Output: [3,1,null,null,2]

Explanation:

• 1 və 3 dəyərləri olan qovşaqlar səhvən dəyişdirilir.
• Bu iki dəyəri dəyişdirin və yeni bərpa edilmiş ikili axtarış ağacımız var.

Pin

Input:  root = [3,1,4,null,null,2]

Output: [2,1,4,null,null,3]

Explanation:

• 2 və 3 dəyərləri olan qovşaqlar səhvən dəyişdirilir.
• Bu iki dəyəri dəyişdirin və yeni bərpa edilmiş ikili axtarış ağacımız var.

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Daxili keçid nin İkili Axtarış Ağacı.
2. İkili Axtarış Ağacının Sırasız keçidində O, qovşaq dəyərlərinin ardıcıllığını yaratdı. artan sifariş.
3. İndi, bütün node dəyərlərinin İkili Axtarış Ağacında düzgün yerində nə vaxt olduğunu düşünün. tapaq maksimum prefiks belə sıralanmış ardıcıllıqla. Sonra ardıcıllıqla hər bir tam ədəd üçün bunu asanlıqla müşahidə edə bilərik prefiks maksimum [i] = node dəyəri hazırkı mövqedə.
4. İki node dəyəri dəyişdirildikdə, yuxarıdakı meyarların yerinə yetirilmədiyi bir alt massiv var. Ona görə də biz tapmalıyıq belə alt massivin başlanğıc və son mövqeləri.
5. Düyün dəyərlərini dəyişdirin bu iki mövqedə və ikili axtarış ağacımız bərpa olunur.
6. Rekursiv şəkildə ağacın sıra ilə keçidini yerinə yetirin və tələb olunan alt massivin başlanğıc və son qovşağını tapın.
7. Yuxarıdakı addımda tapılan iki qovşaqlı dəyərləri dəyişdirin.

Kodu

İkili Axtarış Ağacını bərpa edin Leetcode C++ Həlli:

class Solution {
public:
    int maxi = INT_MIN;
    TreeNode* node1 = nullptr;
    TreeNode* node2 = nullptr;
    void inorder(TreeNode* root){
        if(root==nullptr){
            return;
        }
        inorder(root->left);
        maxi = max(maxi,root->val);
        if(maxi==root->val){
            if(node2==nullptr){
                node1 = root;
            }
        }
        else{
            node2 = root;
        }
        inorder(root->right);
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(node1->val,node2->val);
    }
};

İkili Axtarış Ağacı Leetcode Java Həllini bərpa edin:

class Solution {
    private TreeNode first;
    private TreeNode second;
    private TreeNode pre;
    public void recoverTree(TreeNode root) {
        if(root==null) return;
        first = null;
        second = null;
        pre = null;
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }    
    private void inorder(TreeNode root){
        if(root==null) return;
        inorder(root.left);
        if(first==null && (pre==null ||pre.val>=root.val)){
            first = pre;
        }
        if(first!=null && pre.val>=root.val){
            second = root;
        }
        pre = root;
        inorder(root.right);
    }
}

İkili Axtarış Ağacı Leetcode Həllinin Bərpası üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) çünki biz bütün ikili axtarış ağacını bir dəfə keçdik, burada N = ağacdakı qovşaqların ümumi sayı.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O(1) [burada rekursiya yığınına görə boşluqları nəzərə almırıq] çünki biz daimi boşluqdan istifadə edirik.

Referans: https://en.wikipedia.org/wiki/Binary_search_tree