•
문제 설명 : 제공되는 sub 트리가 root 트리의 subtree가 될 수 있는지 여부 반환
•
풀이 방법
◦
두 노드를 사용하여 하위트리인지 확인하는 방식까지 동일하게 생각하였지만… 예외 처리가 어려워 solution을 참고하였다.
▪
결론은, 너무 어렵게 생각했다는 점이다.
▪
그렇게 복잡한 조건을 일일히 확인하지 않고, Node를 사용한 문제는 아래와 같이 확인하면 될 것 같다
•
diff_tree
1.
None인가? → 어찌보면 가장 중요하다. None 처리로 인해 가독성이 떨어지는 코드가 많이 작성되기 때문이다.
2.
값이 존재하는가?
3.
값이 동일한가? (비교 시)
4.
재귀(좌/우)
•
isSubtree
1.
현재 노드가 None이 아닌가?
2.
현재 노드에 대한 탐색(다른 문제라면, 현재 노드에 대한 처리가 들어가면 된다. 이 부분에서 하위 노드의 탐색 진행 여부를 결정한다)
3.
하위 노드에 대한 탐색
•
시간복잡도 : → 정확하게는 (Root 트리 노드수 * sub 트리 노드수)
•
성공 코드
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def diff_tree(node1, node2):
# 둘 다 None인지 확인
if not node1 and not node2:
return True
# 둘 중 하나만 값을 가졌는지 확인
if not node1 or not node2:
return False
# 두 값이 다른지 확인
if node1.val != node2.val:
return False
return diff_tree(node1.left, node2.left) and diff_tree(node1.right, node2.right)
# 노드가 존재하는 경우만 진행
if root:
# 현 노드 하위가 subRoot와 일치할 때
if diff_tree(root, subRoot):
return True
# 하위 탐색
left = self.isSubtree(root.left, subRoot) if root.left else False
right = self.isSubtree(root.right, subRoot) if root.right else False
return left or right
return False
Python
복사