Hər Node Leetcode Həllində Növbəti Sağ Göstəricilərin Yerləşdirilməsi

Problem bəyanat

The Hər Node LeetCode Həllində Növbəti Sağ Göstəricilərin Yerləşdirilməsi – “Hər Düyündə Növbəti Sağ Göstəricilərin Yerləşdirilməsi” mükəmməl ikili ağacın kökünü nəzərə alaraq, qovşağın hər bir növbəti göstəricisini onun növbəti sağ qovşağına doldurmağımız lazım olduğunu bildirir. Növbəti sağ node yoxdursa, növbəti göstəricini null olaraq təyin edin.

Misal:

Input:  root = [1,2,3,4,5,6,7]

Output: [1,#,2,3,#,4,5,6,7,#]

Explanation:

• Daha yaxşı başa düşmək üçün yuxarıdakı diaqramı yoxlayın.

Input:  []

Output: []

Explanation:

• Kök null göstəricidir, buna görə də [].

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Genişlik-İlk Axtarış.
2. Hər səviyyədə saxlayın növbənin ölçüsü cari səviyyədə mövcud olan qovşaqların sayını bildirir.
3. Bu qovşaqlar üzərində təkrarlayın və qovşağın növbəti göstəricilərini əlaqələndirin.
4. Həmçinin, bütün qovşaqları yerinə yetirərək növbəti səviyyəyə itələyin səviyyəli sifariş keçidi.
5. Hər bir qovşağın növbəti göstəricilərini birləşdirdikdən sonra mükəmməl ikili ağacın kökünü qaytarın.

Kodu

C++ Həlli:

class Solution {
public:
    Node* connect(Node* root) {
        if(root==nullptr){
            return root;
        }
        queue<Node*> q;
        q.push(root);
        
        while(!q.empty()){
            int sz = q.size();
            Node* prev = nullptr;
            while(sz--){
                Node* curr = q.front();
                q.pop();
                if(prev!=nullptr){
                    prev->next = curr;
                }
                prev = curr;
                if(curr->left!=nullptr){
                    q.push(curr->left);
                }
                if(curr->right!=nullptr){
                    q.push(curr->right);
                }
            }
        }        
        return root;
    }
};

 Java Həlli:

class Solution {
    public Node connect(Node root) {
        if(root == null){
            return null;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            Node rightNode = null;
            for(int i = q.size(); i > 0; i--) {
                Node curr = q.poll();
                curr.next = rightNode;
                rightNode = curr;
                if(curr.right != null) {
                    q.offer(curr.right);
                    q.offer(curr.left);
                }
            }
        }
        return root;        
    }
}

Hər Node Leetcode Həllində Növbəti Sağ Göstəricilərin Yerləşdirilməsi üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (N) burada N = qovşaqların ümumi sayı, çünki biz hər bir node ən çox 2 dəfə daxil oluruq.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N) ildən Queue yuxarıdakı mükəmməl ikili ağacın geniş-ilk axtarışını yerinə yetirmək üçün istifadə olunur.