Leet Code - 100. Same Tree(C++)

예제: Same Tree

문제
Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Example 2:

Example 2:

풀이

이진트리 두 개가 주어졌을 때, 이들이 같은지 다른지 true, false를 반환하는 문제이다.
오랜만에 한번에 푼 문제인데, 필자는 재귀함수로 풀어보았다.

트리가 같은지만 확인하면 되기 때문에, 왼쪽 오른쪽 순서대로 자식노들을 타고 가며 같지 않으면 바로 false를 return해주는 형태이다.

전체적인 소스코드는 아래와 같다.

소스 코드

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
	bool isSameTree(TreeNode* p, TreeNode* q) {

		if (p == NULL && q == NULL) return true;
		if ((p != NULL && q == NULL) || (p == NULL && q != NULL)) return false;
		if (p->val != q->val) return false;

		return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
	}
};

풀이 후기

드디어!!
Runtime: 0 ms, faster than 100.00% of C++ online submissions for Same Tree.
Memory Usage: 9.6 MB, less than 100.00% of C++ online submissions for Same Tree.
결과를 받았다 😁
돌릴때마다 다르긴 하겠지만, 그래도 뿌듯하다(다시 돌리면 다른 결과가 나올까봐 못돌리는 중...).

이런거에 아주 뿌듯한걸 보면 새벽감성이 충만한 새벽시간대라 그런지도 모르겠다.