Skip to content

leetcode

536 - Symmetric Tree

너무 오랜만에 풀어보니까 감이 좀 떨어지는 것 같습니다.

 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 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) {}
 * };
 */
#include<queue>
#include<vector>

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            int cur_len = q.size();
            vector<TreeNode*> tmp;
            for(int i=0; i<cur_len; ++i)
            {
                TreeNode* cur = q.front();
                tmp.push_back(cur);

                if(!cur)
                {
                    q.pop();
                    continue;
                }

                q.push(cur->left);
                q.push(cur->right);
                q.pop();
            }
            if(!isSymmetricLine(tmp))
                return false;
        }
        return true;
    }

private:
    bool isSymmetricLine(vector<TreeNode*> lst)
    {
        printf("\n");
        bool rslt = true;
        int len = lst.size();
        for(int i=0; i<len/2; ++i)
        {
            if(lst[i]==nullptr && lst[len-i-1]==nullptr)
            {
                continue;
            }else if(lst[i]==nullptr && lst[len-i-1]!=nullptr)
            {
                rslt = false;
                break;
            }else if(lst[i]!=nullptr && lst[len-i-1]==nullptr)
            {
                rslt = false;
                break;
            }else
            {
                if(lst[i]->val != lst[len-i-1]->val)
                {
                    printf("%d, %d\n", lst[i]->val, lst[len-i-1]->val);
                    rslt = false;
                    break;
                }    
            }
        }
        return rslt;
    }

};