LeetCode : 100. Same Tree

아주 간단하게 재귀 방식을 통해서 풀 수 있는 문제였다.

 

[메인 로직]

기본적으로 재귀를 root->left->right 순서로 PreorderTraversal을 진행했다.

1. 각 트리의 노드가 둘 다 NULL일 경우, true를 반환한다.(루트의 경우 NULL이면 어차피 left, right으로 뻗어가는 가지가 아니기 때문에 같은 형태임을 알 수 있다.)

2. 각 트리의 노드가 둘 중 하나만 NULL이라면, 같은 구조의 트리가 아니므로 false를 반환한다.

3. 각 트리의 노드의 값이 다르다면, 노드의 값이 다르므로 false를 반환한다.

4. 이후, 왼쪽 서브트리, 오른쪽 서브트리로 순환한다.

 

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 루->왼->오
        if(p==NULL && q==NULL) return true;
        if(p==NULL || q==NULL) return false;
        if(p->val != q->val) return false;
        
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};