[Leetcode] 100. Same Tree

Identifying the Problem

주어진 두 개의 이진트리 p, q를 비교해 같은 지 다른 지 비교해

같으면 true, 다르면 false를 return 한다.

Organizing thoughts

크게 두 가지 방법이 있는데,

1. 94번 문제의 p q 각각 answer를 만들고, answer끼리 비교한다.

2. p, q 둘 다 중위순회하면서 서로 같은지 비교하고, 다를 경우 false 가 되게한다.

 

2번이 더 간단하기에 2번을 채택했다.

Sourcecode

bool checkTree(struct TreeNode* p, struct TreeNode* q);

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if (!p && !q) return true; // 둘다 null                 
    else if (!p || !q) return false; //둘 중 하나만 null (xor)
    return checkTree(p, q);
}

bool checkTree(struct TreeNode* p, struct TreeNode* q) 
{
    if (!p && !q) return true; // both are null
    else if (!p || !q) return false; // one is null
    
    if (p->val != q->val || !checkTree(p->left, q->left) || !checkTree(p->right, q->right)) 
    	return false;
    
    // 1조건은 단순히 두 값이 다를 때
    // 2,3조건은 이중부정을 이용해 !false true 니깐, false 를 리턴 
    
    return true;
}