[leetCode] 101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/description/?envType=problem-list-v2&envId=breadth-first-search

Symmetric Tree - LeetCode

 

해당 이진트리 구조가 주어졌을 때 그 구조가 중심을 기준으로 대칭인지 확인하는 문제이다.

아래 코트는 내가 작성했던 내용의 코드이다.

/**
 * 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>

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;

        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);

        while(!q.empty())
        {
            TreeNode* tn1 = q.front(); q.pop();
            TreeNode* tn2 = q.front(); q.pop();

            if(tn1 == nullptr && tn2 ==nullptr) continue;

            if(!tn1 || !tn2 || tn1->val != tn2->val) return false;

            q.push(tn1->left);
            q.push(tn2->right);

            q.push(tn1->right);
            q.push(tn2->left); 

        }

        return true;
    }
};

처음 생각이 든 것은 "하나의 노드마다 일일히 검사해야 하지 않을까?" 생각이 들어서 queue를 이용해, 풀어봤다.

 

전개 방식은 아래와 같다. 

1. 먼저 root 노드의 좌,우 노드를 queue에 집어 넣는다.

2. queue가 다 떨어지면, 검사가 끝났음을 나타내기에, while문을 사용해 돌린다.

3. queue의 각각 요소들을 꺼내어 두 값을 체킹한다.

4. 만약 두 요소들의 값이 다르면 바로 false로 리턴하고, 그 아래 노드들까지 전부 queue로 넣어서 다음 비교 로직에 넣어 사용한다.

 

아래는 다른 사람들의 코드이다. 

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return isMirror(root->left, root->right);
    }

private:
    bool isMirror(TreeNode* n1, TreeNode* n2) {
        if (n1 == nullptr && n2 == nullptr) {
            return true;
        }
        
        if (n1 == nullptr || n2 == nullptr || n1->val != n2->val ) {
            return false;
        }
        
        return isMirror(n1->left, n2->right) && isMirror(n1->right, n2->left);
    }
};

 

확실히 처음부터 left, right를 다르게 검사해 내려가면 되는 문제였는데 내가 너무 복잡하게 생각하지 않았나 생각이 든다.