Leetcode - 반복 되 는 하위 트 리 찾기

제목 설명
두 갈래 나 무 를 주 고 반복 되 는 모든 하위 나 무 를 되 돌려 줍 니 다.같은 종류의 중복 서브 트 리 에 대해 서 는 그 중 임의의 뿌리 결산 점 으로 돌아 가면 된다.
두 그루 의 나무 가 중복 되 는 것 은 같은 구조 와 같은 결점 치 를 가지 고 있다 는 것 을 말한다.
예시 1:

다음은 두 개의 중 복 된 하위 트 리 입 니 다.

      2
     /
    4

화해시키다

따라서 반복 되 는 하위 나무의 뿌리 결산 점 을 목록 으로 되 돌려 야 합 니 다.
사고
언뜻 보기 에는 좀 번 거 롭 고 어디서부터 시작 해 야 할 지 모 르 겠 지만 이 문제 자체 가 중요 한 문제 라 고 생각 하기 쉽다. 저 장 된 데이터 구 조 는 해시 표 이다. 그리고 문 제 는 중복 되 는 서브 트 리 를 찾 아야 한다. 즉, 우리 가 해시 표 에 저장 해 야 할 요 소 는 모든 나무 이다. 그러면 문 제 는...나무 한 그루 를 어떻게 표시 하 느 냐, 혹은 나무 가 중복 되 는 지 여 부 를 어떻게 판단 하 느 냐 하 는 문제.
여기 서 명확 한 결론 이 필요 합 니 다. 앞 순 서 는 같은 나 무 를 옮 겨 다 니 고 나무 구조 도 같 습 니 다. (여기 서 옮 겨 다 니 는 결 과 는 잎 노드 가 None 인 잎 노드 를 포함 합 니 다)그럼 잘 됐 네. 각 노드 의 앞 순 서 를 기록 하면 돼.
코드

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

class Solution(object):
    def DLR(self, root, orders, res):
        if root is None:
            return '#END#'
        #   ，     
        my_order = str(root.val) + '\t' + self.DLR(root.left, orders, res) + '\t' + self.DLR(root.right, orders, res)
        if orders.get(my_order, 0) == 1:
            res.append(root)
        orders[my_order] = max(1, orders.get(my_order, 0) + 1)
        return my_order
    def findDuplicateSubtrees(self, root):
        """
        :type root: TreeNode
        :rtype: List[TreeNode]
        """
        orders = dict()
        res = list()
        self.DLR(root, orders, res)
        return res

참고
1. leetcode： https://leetcode-cn.com/explore/learn/card/hash-table/206/practical-application-design-the-key/823/

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

Leetcode - 반복 되 는 하위 트 리 찾기

좋은 웹페이지 즐겨찾기