652. Find Duplicate Subtrees (leetcode)

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

root 이진 트리가 주어지면 모든 중복 하위 트리를 반환합니다 .

각 종류의 중복 하위 트리에 대해 그 중 하나 의 루트 노드만 반환하면 됩니다 .

두 개의 트리가 동일한 노드 값을 갖는 동일한 구조를 갖는 경우 중복 트리 입니다 .

이진 트리가 있을 때 중복된 트리 노드를 반환하는 문제 일단 반환값을 트리 객체를 리스트 안에 넣어서 리턴한다는 점,
그리고 중복되는 하위 노드를 모두 반환해야 한다 1번처럼 2-4 노드가 같지만 2-4 ,4를 반환하는 거처럼

2-4-5-7-1처럼 생기면 24571, 4571, 571 ,71 , 1처럼 모두 리턴해야 함

처음 접근을 한 층씩 내려가면서 루트 객체를 딕셔너리에 담아 같은 게 나오면 리턴하려 했지만 아마 트리 객체가 값은 같아도 저장하면 다른 객체로 인식해서 비교가 불가능했다 그래서 트리의 모든 값을 리턴하는 함수를 만들어 노드를 내려갈 때마다 확인함 모든 값을 리턴하여 비교하는 거라 정확하지만 모든 값을 반복하는 거라 아마 n^2 정도가 걸리는 듯

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        d={}
        d1=[]
        d2={}
        def f1(root,p):
            if root==None:
                p.append(None)
                return
            p.append(root.val)
            f1(root.left,p)
            f1(root.right,p)
            return p
        def f(root):
            if root==None:
                return 
            d.setdefault(root.val,[])
            lk=f1(root,[])
            d2.setdefault(tuple(lk),1)
            if (lk in d[root.val]) and d2[tuple(lk)]:
                d1.append(root)
                d2[tuple(lk)]=0
            d[root.val].append(lk)
            f(root.left)
            f(root.right)
        f(root)
        return d1