[1스4코2파] # 165. LeetCode Pattern 572. Subtree of Another Tree

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (165차)
[4코1파] 2023.01.13~ (157일차)
[1스4코1파] 2023.04.12~ (68일차)
[1스4코2파] 2023.05.03 ~ (47일차)

Today :

2023.06.15 [165일차]
LeetCode Patterns
572. Subtree of Another Tree

572. Subtree of Another Tree

https://leetcode.com/problems/subtree-of-another-tree/description/

문제 설명

binary tree 2개가 주어지는 데 하나는 root, 하나는 subRoot 이다.
root의 자식노드들 중에 하나가 subRoot 와 같은게 있으면 True, 없으면 False를 return

문제 풀이 방법

ㅡㅡ그냥 단순하게 queue에 넣고 popleft 해서
root.left 랑 비교하고 그렇게 했는데 안됐다..
다른 solution 보니까 뭐 하나하나 다 비교를 해야되네 이거는 개노답임
dfs로 풀었고, 안에 노드의 원소를 체크하는 same 함수까지 넣어서
넣고넣고넣고넣고 무슨 함수가 3개
더 간단하게 풀 수 있을것 같은데 머리가 부족함 low iq

내 코드

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def dfs(node):
            def same(p,q):
                if not p and not q:
                    return True
                if not p or not q or p.val!=q.val:
                    return False
                return same(p.left, q.left) and same(p.right, q.right)
            if not node:
                return False
            if node.val == subRoot.val and same(node,subRoot):
                return True
            return dfs(node.left) or dfs(node.right)
        return dfs(root)

증빙

여담

트리지옥