101. Symmetric Tree

發表於 | 分類於

problem

solution

option 1 - dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool sym(TreeNode *l, TreeNode *r){
        if(!l && !r) return true;
        if(!l || !r) return false;
        if(l->val != r->val) return false;
        return sym(l->left, r->right) && sym(l->right, r->left);
    }
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return sym(root->left, root->right);
    }
};

option 2 - bfs

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
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        int depth = 1;
        queue<pair<TreeNode*,int>> q  ;
        q.push({root, depth});
        while(!q.empty()){
            vector<int> rec;
            int size = q.size();
            for(int i=0;i<size; ++i){
                auto [p,d] = q.front();
                q.pop();
                
                if(p->left) {
                    q.push({p->left, d+1});
                    rec.push_back(p->left->val);
                }
                else rec.push_back(-101);
                if(p->right){
                    q.push({p->right, d+1});
                    rec.push_back(p->right->val);
                } 
                else rec.push_back(-101);
            }
            // check is palindrome
            int l=0, r = rec.size()-1;
            while(l<r){
                if(rec[l++]!=rec[r--]) return false;
            }
            
        }
        return true;
    }
};