Simmetrik Ağac LeetCode Həlli Leetcode Həlli

Problem bəyanat

The Simmetrik Ağac LeetCode Həlli – “Simmetrik ağac” ikili ağacın kökü verildiyini bildirir və verilmiş ikili ağacın bir ağac olub olmadığını yoxlamaq lazımdır. öz güzgüsü(mərkəzi ətrafında simmetrik) ya yox? Əgər Bəli, biz doğru, əks halda yalan qayıtmalıyıq.

Misal:

Pin

 

Qeyd edək ki, eyni rəngli qovşaqlar eyni node dəyərinə malikdir. İkili ağac simmetrik ağacdır.

 

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

Output: true

Explanation:

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

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

Output: false

Pin

Explanation:

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

Yanaşma

Idea:

1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Recursion.
2. İndi, əgər ağac simmetrik adlanır sol alt ağac sağ alt ağacın güzgü əksi olmalıdır.
3. Həmçinin, iki ağacın bir-birinə güzgü olduğu deyilir, əgər:
   1. Onların kökləri eyni dəyərdədir.
   2. Hər ağacın sağ alt ağacı başqa bir ağacın sol alt ağacının güzgüdəki əksidir.
4. Beləliklə, rekursiyanı aşağıdakı hallarda yerinə yetirin:
   1. Üçün baza işi:
      • Hər iki kök qovşağı null göstəricilərdirsə, doğru qaytarın.
      • Əgər onlardan tam olaraq biri boş qovşaqdırsa, yalanı qaytarın.
   2. In ümumi:
      • Kök qovşaqları eyni dəyərə malik olmalıdır və,
      • Sol alt ağac və sağ alt ağac bir-birinə münasibətdə güzgü əksi olmalıdır.
      • Beləliklə, kök qovşağının dəyərləri eyni və sol və sağ alt ağaclar simmetrik olarsa, doğru qaytarın.

Kodu

Simmetrik Ağac Leetcode C++ Həlli:

class Solution {
public:
    bool check(TreeNode* root1,TreeNode* root2){
        if(root1==nullptr or root2==nullptr){
            return root1==root2;
        }
        return root1->val==root2->val and check(root1->left,root2->right) and check(root1->right,root2->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }
};

Simmetrik Ağac Leetcode Java Həlli:

class Solution {
    private boolean check(TreeNode root1,TreeNode root2){
        if(root1==null || root2==null){
            return root1==root2;
        }
        return root1.val==root2.val && check(root1.left,root2.right) && check(root1.right,root2.left);
    }
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
}

Simmetrik Ağac Leetcode Həlli üçü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 giriş 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(N) [rekursiv zəngləri də nəzərə alaraq]. Rekursiv çağırışların sayı ağacın hündürlüyü ilə məhdudlaşır və ən pis halda ağac xətti ola bilər. Beləliklə, Kosmik Mürəkkəblik O(N).