【 힘 단추 일 기 】 501 이 진 트 리 의 개수 검색 | 사전 값 에 따라 정렬

제목 설명
같은 값 을 가 진 이 진 검색 트 리 (BST) 를 지정 하여 BST 의 모든 중 수 를 찾 습 니 다 (주파수 가 가장 높 은 요소 가 나타 납 니 다).
알림: 개수 가 1 개 를 넘 으 면 출력 순 서 를 고려 하지 않 아 도 됩 니 다.
진급: 추가 공간 을 사용 하지 않 아 도 됩 니까?(재 귀적 으로 발생 하 는 암시 적 호출 스 택 의 비용 이 계산 되 지 않 는 다 고 가정 합 니 다)
알고리즘 사고
NAIVE
첫 번 째 단 계 는 사전 으로 계산한다.

class Solution:
    def findMode(self, root: TreeNode):
        if not root:return []
        di=collections.defaultdict(int)
        def bfs(root,di={}):
            if not root:return []
            di[root.val]+=1
            bfs(root.left,di)
            bfs(root.right,di)
        bfs(root,di)

두 번 째 단 계 는 사전 에 값 에 따라 정렬 하여 중 수 를 목록 에 넣 습 니 다.

        d1=sorted(di.items(), key=lambda x: x[1])
        l,MAX=d1.pop()
        ls=[]
        ls.append(l)

세 번 째 단 계 는 최대 치 에 따라 다른 중수 가 있 는 지 판단 한다.

        while d1:
            if d1[-1][1]==MAX:
                ls.append(d1.pop()[0])
            else:break
        return ls

실행 시: 60 ms, 모든 Python 3 제출 에서 80.28% 의 사용 자 를 격파 하 였 습 니 다.
특히 이 방법 은 모든 나무의 중 수 를 구 하 는 데 적합 하 다.
IMPROVE
검색 트 리 의 중간 순 서 를 기반 으로 배열 을 늘 리 는 것 이 므 로 O (1) 공간 만 사용 하 는 방법 이 필요 합 니 다.

class Solution:
    def findMode(self, root: TreeNode):
        if not root:return []
        res=[]
        pro=None
        curtime,maxtime=1,0
        def inorder(root):
            nonlocal pro
            nonlocal curtime
            nonlocal maxtime
            if not root:return
            inorder(root.left)
            if pro:
                if root.val == pro.val:curtime+=1
                else:curtime=1
            pro = root
            if curtime==maxtime:res.append(root.val)
            elif curtime>maxtime:
                res.clear()
                res.append(root.val)
                maxtime=curtime

            inorder(root.right)
        inorder(root)
        return res

！res 는 서열 이 므 로 직접 수정 할 수 있 습 니 다.
！반드시 언급 해 야 할 것 은 원래 앞의 노드 pro 를 정 의 된 inorder 함수 에 넣 었 지만 측정 예 [1, None, 2, 2] 에 대해 3 층 의 2 에서 2 층 으로 영원히 뛰 어 올 랐 을 때 pro 는 루트 노드 1 을 가리 키 는 것 이 되 었 기 때문에 출력 값 은 항상 [1, 2, 2] 이다.
이 유 를 몰랐어!화가 나 죽겠다.나 는 여전히 귀환 의 내 면 을 완전히 파악 하지 못 했다.해결 방법: 선행 값 을 저장 하 는 pro 변 수 를 내장 함수 밖의 외부 함수 변수 로 바 꾸 고 nonlocal 성명 을 통 해 수정 합 니 다.
보충 해 보 니 curtime, maxtime 도 반대로 뛰 고 단숨에 외부 변수 로 밝 혀 졌 다.
！위의 문제 와 같이 재 귀적 정 의 를 결합 하면 내장 함수 의 모든 변 수 를 재 귀적 으로 호출 할 때 그 당시 의 상 태 를 push 로 스 택 에 넣 었 을 수 있 습 니 다. 다음 층 에서 수정 을 하 더 라 도 스 택 이 돌아 올 때 원래 의 상 태 를 회복 하 였 습 니 다.
！

            if pro:
                if root.val == pro.val:curtime+=1
                else:curtime=1

대체 가능

            if pro:curtime=curtime+1 if root.val == pro.val else 1

실행 시: 52 ms, 모든 Python 3 제출 에서 97.21% 의 사용 자 를 격파 하 였 습 니 다.