[LeetCode] Symmetric Tree

 

https://leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

문제

해설 

Tree가 Symmetric 즉 대칭적인지 판단하면 된다.

이 문제는 두가지 방법으로 풀 수 있다.

1. recursive한 방법

2. iterative 한 방법

 

1. recursive한 방법 

트리가 대칭적이려면 다음과 같은 조건이 필요하다

• 2번 혹은 3번 하나만 존재시 대칭이 아니다.
• 2번 && 3번이 둘다 없을 경우 대칭이다.
• 2번&& 3번이 둘다 존재한다.
  • 2번과 3번 노드의 값이 같을 경우
    • 4번과 7번노드 && 5번과 6번노드가 같아야 대칭이다.
    • 아니면 대칭이 아니다.
  • 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 isSymmetric(TreeNode* root) {
        if(root == NULL)
            return true;
        else
           return isSubSymmetric(root->left,root->right);
    }
    bool isSubSymmetric(TreeNode* leftSide, TreeNode* rightSide)
    {
        if(leftSide == NULL && rightSide == NULL) // 자식노드 둘다 없는 경우
            return true;
        else if(leftSide == NULL || rightSide == NULL) // 하나만 있을 경우 대칭이 아님
            return false;
        else
        {
            if(leftSide->val == rightSide->val) //둘다 있을 경우 값을 비교하여 같을 경우
                return isSubSymmetric(leftSide->left,rightSide->right) and isSubSymmetric(leftSide->right, rightSide->left);
            else
                return false;// 둘다 있는데 값이 다를 경우 대칭이 아니다.
        }   
                
    }
};