문제

최상위 root노드를 기준으로
하위 left묶음 트리와 right묶음 트리가 거울반전(미러링)된 상태인지 확인하면 되는 문제임

풀이

재귀로 풀려다가 감이 안와서
먼저 DFS, BFS로 풀려고하다가 답이 안나와서 포기함...

그래서 답지를 봄

근데 답이 너무 간단해서 개화남

개빡침 지금
그래서 얼음물 들이키고 포스팅하는중

그냥 진짜 간단함

root를 기준으로 미러링된 이진트리인지 확인하는거거덩?

항상 재귀를 할땐, 그 경우에서 답이 나오는거처럼 풀면됨

위 문제의 핵심은 다음과 같음

1. 왼쪽 트리의 left가 오른쪽 트리의 right에 위치해야한다
2. 왼쪽 트리의 right가 왼쪽 트리의 left에 위치해야한다

그래서 핵심 로직은 다음과 같음

bool same(TreeNode* left, TreeNode* right)
{
	return same(left->left, right->right) &&
    	   same(left->eight, right->left);
}

그럼 이제 종료조건을 찾아야함

3가지 경우가 생김

1. 두 노드가 모두 null일때
2. 두 노드가 모두 null이 아닐때,
3. 두 노드 중 한개만 null일때

여기서 중요한건
left->left, right->right와
left->right, right->left를 비교한다는거임

즉,

1. 두 노두가 모두 null인경우는 미러링이 되었다고 볼 수 있음
   l->left = null == r->right = null이라는 말과
   l->right = null == r->left = null이라는 말과 같음
2. 두 노드 모두 null이 아닐때, 두 노드의 값이 다르다면 그건 미머링이 되었다고 볼 수 없음
   위의 1번에서 설명한거처럼 각 경우를 생각해보면 됨
3. 두 노드 중 1개만 null일때, 마찬가지로 미러링이 되었다고 볼 수 없음

근데 2번 종료조건을 확인하려면 3번 종료조건이 우선시 되어야함
둘중 하나라도 null이면 return을 시켜야 값 확인이 확실하게 되긌지?

따라서 종료코드를 추가하면 다음과 같음

bool same(TreeNode* l, TreeNode* r)
{
	//1. 두 노드가 모두 null일때
    if(!l && !r) return true;
    
    //3번 종료조건과 바꾼...
    //2. 두 노드 중 하나라도 null일때
    if(!l || !r) return false;
    
    //2번 종료조건과 바꾼...
    //3. 두 노드 모두 존재하고, 값이 다른경우
    if(l->val != r->val) return false;
    
	return same(l->left, r->right) &&
    	   same(l->right, r->left);
}

따라서 정답은 다음과 같음

정답

class Solution {
public:
    bool same(TreeNode* l, TreeNode* r)
    {
	    //1. 두 노드가 모두 null일때
        if(!l && !r) return true;
    
        //3번 종료조건과 바꾼...
       //2. 두 노드 중 하나라도 null일때
        if(!l || !r) return false;
    
        //2번 종료조건과 바꾼...
        //3. 두 노드 모두 존재하고, 값이 다른경우
        if(l->val != r->val) return false;
    
	    return same(l->left, r->right) &&
    	       same(l->right, r->left);
    }

    bool isSymmetric(TreeNode* root) 
    {
        if(!root) return true;

        return same(root->left, root->right);
    }
};