문제 URL : https://leetcode.com/problems/subtree-of-another-tree/
Subtree of Another Tree - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제 접근법 : root의 subtree중 subRoot와 같은것이 있는지 확인합니다.
확인하는 방법은 간단합니다. root의 값이 subroot와 같으면 같은모양인지
확인하면서 왼쪽자식의값과 오른쪽자식의값이 같은지 확인합니다. 다른게 있다면 바로 false를 해주면되고 전부 같으면 true로 반홥합니다.
이때 모양이 무엇인지 잘모르겠다면 모양은 왼쪽자식이 존재하는지 혹은 오른쪽 자식이 존재하는지 혹은 둘다 있거나 혹은 둘다 없거나 즉 4가지 경우의 수밖에 존재할수 없습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution {
public:
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if (!root) return false;
if (root->val == subRoot->val) {
return sametree(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
bool sametree(TreeNode* root, TreeNode* subRoot) {
if (!subRoot) return true;
if (root->val != subRoot->val) return false;
if (!sameShape(root, subRoot)) return false;
return sametree(root->left, subRoot->left) && sametree(root->right, subRoot->right);
}
bool sameShape(TreeNode* root, TreeNode* subRoot) {
int l = 0, r = 0;
l |= root->left ? 1 : 0;
l |= root->right ? 2 : 0;
r |= subRoot->left ? 1 : 0;
r |= subRoot->right ? 2 : 0;
return l == r;
}
};
|
cs |
모르는점 혹은 궁금한점 혹은 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.
'LeetCode' 카테고리의 다른 글
| LeetCode 103. Binary Tree Zigzag Level Order Traversal (0) | 2021.08.03 |
|---|---|
| LeetCode 686. Repeated String Match (0) | 2021.07.31 |
| LeetCode 459 Repeated Substring Pattern (0) | 2021.07.31 |
| LeetCode 38 Count and Say (0) | 2021.07.15 |
| LeetCode ZigZag Conversion (0) | 2021.07.14 |
