(Leetcode) 572 - Subtree of Another Tree
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/subtree-of-another-tree/description/
내가 작성한 풀이
public class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
if (isSubtreeStrict(root, subRoot)) {
return true;
}
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
}
public boolean isSubtreeStrict(TreeNode root, TreeNode subRoot) {
if (root == null && subRoot == null) {
return true;
}
if (root == null || subRoot == null) {
return false;
}
return root.val == subRoot.val && isSubtreeStrict(root.left, subRoot.left) && isSubtreeStrict(root.right, subRoot.right);
}
}
케이스를 두가지로 나눴다.
dfs로 다음과 같이 진행한다.
- 해당 노드의 값이 subtree의 root 값과 일치하는 경우
- 나머지 하위 노드들도 일치하는지 검색한다.
- 그렇지 않은 경우
- dfs 로 해당 노드의 root 값이 subtree와 일치하는 노드가 있을 때 까지 탐색한다.
- 찾지 못하면 false를 반환한다.
- dfs 로 해당 노드의 root 값이 subtree와 일치하는 노드가 있을 때 까지 탐색한다.
TC, SC
시간 복잡도는 O(n * m)이고 공간 복잡도는 O(n + m), 단 입력 트리가 balanced되어 있다면 O(logn + logm) 이다. 여기서 n 은 Root 의 노드 수, m 은 subTree 의 노드 수 이다.
submit 결과
