Κοινή χρήση τεχνολογίας

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Πρόλογος

Στο κεφάλαιο Binary Tree, ξεκινήστε να εξασκείτε τη λειτουργία των δυαδικών δέντρων.
Εγγραφή 42 [101 Συμμετρικό Δυαδικό Δέντρο].
να συνεχίσει.

---

1. Ανάγνωση θεμάτων

Σας δίνουμε τη ρίζα του ριζικού κόμβου ενός δυαδικού δέντρου, Ελέγξτε αν είναι αξονικά συμμετρικό。

Παράδειγμα 1:

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

Παράδειγμα 2:

输入：root = [1,2,2,null,3,null,3]
输出：false
1
2

ίχνος:

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
1
2

Για προχωρημένους: Μπορείτε να χρησιμοποιήσετεΑναδρομή και επανάληψηΔύο τρόποι για να λυθεί αυτό το πρόβλημα;

---

2. Προσπαθήστε να συνειδητοποιήσετε

Ιδέα 1

Δοκιμάστε να χρησιμοποιήσετε πρώτα την αναδρομή. Πυρήνας: Ποια είναι τα κριτήρια για την κρίση της αξονικής συμμετρίας;

Αναδρομή: Καλέστε τον εαυτό σας.Δεν βρέθηκε ακόμη διπλή λογική：

• Προσδιορίστε αριστερά==δεξιά; Η εισαγωγή του υποδέντρου είναι εσφαλμένη.
• Το αριστερό υποδέντρο πηγαίνει αριστερά, στο κέντρο, και το δεξί υποδέντρο πηγαίνει δεξιά, αριστερά, στο κέντρο. Είναι ίσες οι ακολουθίες; Αλλά αυτό είναι για ολόκληρο το δέντρο. Η εισαγωγή του υποδέντρου είναι επίσης λάθος.

Ιδέα 2

Χρησιμοποιήστε μια επαναληπτική προσέγγιση για την αλλαγή. Χρησιμοποιήστε τη διέλευση σειράς επιπέδου.
Μετά τη λήψη του αποτελέσματος της ακολουθίας στρώσεων, κρίνεται ότι κάθε στρώμα είναι ένας ζυγός αριθμός και ίσος μετά την αντίστροφη. Αλλά για παράδειγμα δύο, αυτό δεν είναι αλήθεια επειδή ο μηδενικός δείκτης αποκλείεται.
Η ιδέα δεν λειτουργεί.

Συνοψίζω:Αν και γνωρίζουμε ότι πρέπει να αναζητήσουμε συμμετρία, δεν έχουμε ένα ενιαίο πρότυπο για να κρίνουμε τη συμμετρία.。

---

3. Ιδέες αναφοράς

Σύνδεσμος αναφοράς

Μαθησιακό Περιεχόμενο

• Αξονική συμμετρία: Μπορεί το αριστερό και το δεξί υποδέντρο του ριζικού κόμβου να αναστραφούν ώστε να είναι ίσα; , πώς να συγκρίνετε;
• Λήφθηκε από την εξήγησηΣωστή ιδέα: Αυτή η διέλευση απαιτεί το αριστερό υποδέντρο του ριζικού κόμβου και το δεξί υποδέντρο του ριζικού κόμβου.Τραβέρσα ταυτόχρονα . Μόνο διασχίζοντας δύο υποδέντρα ταυτόχρονα μπορούμε να κρίνουμε αν οι κόμβοι και στις δύο πλευρές είναι ίσοι.
  • Πρώτα, περάστε το αριστερό του αριστερού υποδέντρου και το δεξί του δεξιού υποδέντρου Αυτή τη στιγμή, οι εξωτερικοί κόμβοι κρίνονται ίσοι.
  • Στη συνέχεια, περάστε το δεξί του αριστερού υποδέντρου και το αριστερό του δεξιού υποδέντρου Αυτή τη στιγμή, οι εσωτερικοί κόμβοι κρίνονται ίσοι.
  • Μετά από και τις δύο επιστροφές, και οι δύο είναι αληθείς ταυτόχρονα, υποδεικνύοντας συμμετρία.
• Προσδιορίστε τη σειρά διέλευσης: αριστερά, δεξιά, κέντρο. Αφού επεξεργαστείτε το αριστερό παιδί, επεξεργαστείτε ξανά το δεξί παιδί και επιστρέψτε το αποτέλεσμα στον μεσαίο κόμβο.
• Προσπάθεια υλοποίησηςΑνεπάρκεια ιδεών : Επεξεργαστείτε μόνο το αριστερό υποδέντρο του ριζικού κόμβου και βρείτε ότι η σειρά του δεξιού υποδέντρου του ριζικού κόμβου είναι διαφορετική από το αριστερό υποδέντρο. Δεν μπορείτε να αποκτήσετε ενοποιημένη λογική αναστρέφοντας τη σειρά διέλευσης ή οτιδήποτε άλλο.

Αναδρομική υλοποίηση

Κάθε σχόλιο είναι μια ιδέα.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool iscompare(TreeNode* left,TreeNode* right){ //两边同时遍历，所以两个参数。返回是否相等，用bool类型。
        //确定终止条件
        if(!left && !right) return true;    //同时为空，可以翻转
        else if(!left && right) return false; //一个空，一个不为空。肯定不等
        else if (!right && left) return false;//一个空，一个不为空。肯定不等
        else if(left->val != right->val) return false;//都不为空，但是值不等

        //都不为空，值相等。说明可以继续进行外侧比较、内侧比较，不用return。
        bool outside = iscompare(left->left,right->right);  //同时比较，解决了左右遍历顺序不一样
        bool inside = iscompare(left->right,right->left);
        return outside && inside;   //同时返回true。才能返回true
    }
    bool isSymmetric(TreeNode* root) {
        return iscompare(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Η σειρά διέλευσης ενός δέντρου (αριστερό υποδέντρο) είναι αριστερά στο κέντρο και η σειρά διέλευσης ενός δέντρου (δεξιό υποδέντρο) είναι δεξιά-αριστερό-κέντρο.

Επαναληπτική ιδέα 1

• Επεξεργαστείτε το αριστερό υποδέντρο του ριζικού κόμβου και το δεξί υποδέντρο του ριζικού κόμβου ταυτόχρονα. Είναι διαφορετικό από την προηγούμενη διέλευση.
• Χρήση δομής ουράς: βάλεΟι δύο κόμβοι που θα συγκριθούν τοποθετούνται στην ουρά ταυτόχρονα,ΠάλιΒγάλτε το ταυτόχρονα . Προσδιορίστε εάν οι δύο εξαγόμενοι κόμβοι μπορούν να αναστραφούν. Αν λοιπόν το αριστερό και το δεξί παιδί είναι ελεύθερα, πρέπει επίσης να μπουν στην ουρά.
• Χρησιμοποιήστε τη δομή στοίβας: πρέπει ακόμα να επεξεργαστείτε δύο κόμβους ταυτόχρονα. Υπάρχουν δύο αντικείμενα προς σύγκριση.Βάλτε το ταυτόχρονα και βγάλτε το ταυτόχρονα。

Επαναληπτική υλοποίηση [δομή ουράς]

Η δομή της στοίβας είναι η ίδια.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return false;
        queue<TreeNode*> que;
        que.push(root->left);//放入左子树
        que.push(root->right);//放入右子树
        while(!que.empty()){
            TreeNode* left = que.front(); que.pop();//取出比较对象中的左节点
            TreeNode* right = que.front();que.pop();//取出比较对象中的右节点

            if(!left && !right){    //都是空节点
                continue;
            }else if(!left || !right || left->val != right->val){
                return false;
            }

            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

Περίληψη [Axisymmetric Binary Tree]:

• Είναι ακόμα διέλευση, αλλά η διαφορά είναι:Και τα δύο υποδέντρα πρέπει να διασχίζονται ταυτόχρονα . Δεν είναι σωστό να επαναλαμβάνετε βαθιά σε οποιοδήποτε υποδέντρο.
• Οι συνθήκες για τη σύγκριση αντικειμένων για τον προσδιορισμό του αληθούς: και οι δύο είναι κενές ή οι τιμές είναι ίσες. Τα υπόλοιπα είναι ψευδή.
• Δεν είναι επίσης δυνατή η αναδρομική διέλευση οποιουδήποτε υποδέντρου, επειδή η σειρά της αριστερής και της δεξιάς πλευράς είναι διαφορετική.
• Δεν είναι μια διέλευση επιπέδου τάξης. Εάν πρέπει να διασχίσετε τα επίπεδα διαδοχικά: Λάβετε τα αποτελέσματα κάθε επιπέδου και αντιστρέψτε για να δείτε αν είναι ίσα. Ως εξής (δεν συνιστάται), οι παραπάνω απαντήσεις είναι όλες πολύ καλές.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        vector<vector<int>> level;
        queue<TreeNode*> que;
        if(!root) return false;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur){ //不是空节点
                    que.push(cur->left);
                    que.push(cur->right);
                    vec.push_back(cur->val);
                }else{
                    vec.push_back(INT_MIN);//因为节点的值【-100,100】。用一个最小值代表空。
                }
            }
            level.push_back(vec);
        }
        //获得层序遍历。包含空。空的数值借助INT_MIN代替。
        for(int i = 1;i < level.size();i++){
            vector<int> temp = level[i];
            reverse(temp.begin(),temp.end());
            if(temp != level[i]){
                return false;
            }
        }
        return true;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

Εξάσκηση ερωτήσεων

【100. Ίδιο δέντρο】

1. Τίτλος

Δεδομένων των ριζικών κόμβων p και q δύο δυαδικών δέντρων, γράψτε μια συνάρτηση για να ελέγξετε εάν τα δύο δέντρα είναι ίδια.

Αν δύο δέντραΔομικά το ίδιο και οι κόμβοι έχουν τις ίδιες τιμές, θεωρούνται τα ίδια.

Παράδειγμα 1:

输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2

Παράδειγμα 2:

输入：p = [1,2], q = [1,null,2]
输出：false
1
2

Παράδειγμα 3:

输入：p = [1,2,1], q = [1,1,2]
输出：false
1
2

ίχνος:

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
1
2

Ιδέες

Προσδιορίστε αν δύο δέντρα είναι ίδια. Η δομή είναι η ίδια και οι τιμές είναι ίδιες.

• Τότε πρέπειΜόνο όταν υποβάλλονται σε επεξεργασία δύο δέντρα ταυτόχρονα, μπορεί να υπάρχει ένα αντικείμενο σύγκρισης. . Είναι άχρηστο να διασχίζετε μόνο βαθιά/να κάνετε οποιαδήποτε επέμβαση σε ένα δέντρο.
• Διαφορές από το [101 Symmetric Binary Tree], αντικείμενα σύγκρισης.εδώΤο αριστερό παιδί του αντικειμένου σύγκρισης συγκρίνεται με το αριστερό παιδί συγκρίνεται με το δεξί παιδί . Δίνονται οι παράμετροι για την αναδρομική κλήση.

Κώδικας

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;  //传入节点同时为空，可以对应
        else if(!p && q) return false;//一个空，另一个不是空。不可能对应。
        else if(p && !q) return false;//一个空，另一个不是空。不可能对应。
        else if(p->val != q->val) return false;//值不等，不可能对应。

        bool leftchild = isSameTree(p->left,q->left); 
        bool rightchild = isSameTree(p->right,q->right);
        return leftchild && rightchild;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

【572. Υποδέντρο ενός άλλου δέντρου】

θέμα

Σας δίνονται δύο δυαδικά δέντρα root και subRoot.Ελέγξτε εάν το root περιέχει και το subRoot έχειΊδια δομή και τιμές κόμβων υποδέντρο. Εάν υπάρχει, επιστρέφει true διαφορετικά, επιστρέφει false.

Ένα υποδέντρο ενός δυαδικού δέντρου περιλαμβάνει έναν κόμβο του δέντρου και όλους τους απογόνους αυτού του κόμβου. Το δέντρο μπορεί επίσης να θεωρηθεί ως υποδέντρο του εαυτού του.

Παράδειγμα 1:

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
1
2

Παράδειγμα 2:

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
1
2

ίχνος:

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
1
2
3
4

Ιδέες

(1) Τα υποδέντρα κρίνουν επίσης δύο δέντρα ως ίσα. Μπορείτε να χρησιμοποιήσετε το [100 Ερώτηση Κώδικας Εφαρμογής] για να λύσετε την κρίση ισότητας.
(2) Αλλά πρέπει να βρίσκεται στη ρίζαΊση με την τιμή του ριζικού κόμβου subRoot κόμβος ως ο ριζικός κόμβος του υποδέντρου. Διασχίστε τη ρίζα χρησιμοποιώντας τη σειρά επιπέδου.

Κώδικας

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSame(TreeNode* rootnode,TreeNode* subRootnode){
        if(!rootnode && !subRootnode) return true;
        else if(!rootnode && subRootnode) return false;
        else if(rootnode && !subRootnode) return false;
        else if(rootnode->val != subRootnode->val) return false;

        bool leftchild = isSame(rootnode->left,subRootnode->left);
        bool rightchild = isSame(rootnode->right,subRootnode->right);
        return leftchild && rightchild;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //先找到和subRoot值相等的节点，才有可能相等。得遍历root找到和subRoot值相等的节点，可能作为子树的根节点

        //用层序遍历
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur->val == subRoot->val){
                    bool subtree = isSame(cur,subRoot);
                    if(subtree) return true;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

Σύνοψη πλήρους κειμένου

Πυρήνας: Διασχίστε δύο δέντρα ταυτόχρονα για να προσδιορίσετε το αντικείμενο σύγκρισης. Εκτελέστε αναδρομική υλοποίηση.

Καμία βαθιά διάβαση δέντρου δεν θα δώσει σύγκριση και των δύο πλευρών του αντικειμένου.

(Η διόρθωση είναι ευπρόσδεκτη, αναφέρετε την πηγή κατά την επανεκτύπωση)