Leetcode 742.두 갈래 나무의 가장 가까운 잎사귀 결점

Time: 20190924 Type: Medium

제목 설명

각 결점의 값이 서로 다른 두 갈래 나무와 목표 값 k를 정하고 나무 중 목표 값 k와 가장 가까운 잎 결점을 찾아낸다.
이곳은 잎결점과 최근에 두 갈래 나무에서 이 잎 노드에 도달하려면 행진해야 하는 변수가 다른 잎결점에 도달하는 것보다 가장 적다는 것을 나타낸다.그리고 결점이 아이의 결점이 없을 때 잎결점이라고 부른다.
다음 예에서 입력한 트리는 한 줄씩 평평하게 표시됩니다.실제로 루트는 TreeNode 객체 형식으로 제공됩니다.
예 1:
입력: root = [1, 3, 2], k = 1두 갈래 트리 그림:

          1
         / \
        3   2

출력: 2(또는 3)
설명: 2와 3은 모두 목표 1에서 가장 가까운 잎 노드이다.
예 2:
입력:root = [1], k = 1 출력: 1
해석: 최근의 잎 노드는 뿌리 결점 자체이다.
예 3:
입력:root = [1,2,3,4,null,null,null,5,null,6], k = 2
두 갈래 트리 그림:

             1
            / \
           2   3
          /
         4
        /
       5
      /
     6

출력: 3 해석: 값이 3인 잎 노드는 결점 2에서 가장 가까운 결점이다.
주:
root가 표시하는 두 갈래 나무는 최소 1개의 결점이 있고 최대 1000개의 결점이 있다.매 결점마다 유일한 노드가 있다.val, 범위는 [1,1000]입니다.주어진 두 갈래 나무 중 어떤 결점이 노드를 만든다.val == k.
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/closest-leaf-in-a-binary-tree저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.

생각

사고방식도 DFS를 사용하여 트리를 인접 테이블로 변환하여 나타내는 그림입니다. 이 문제와 863의 차이점은 다음과 같습니다.

잎사귀 결점 기록

BFS 종료 조건은 원형 확산 시 잎사귀 결점을 찾아 종료

반드시 visited 표시를 넣어야 한다. 그렇지 않으면 사순환에 빠질 것이다.
목록을 사용하여 대기열의 쓰기를 시뮬레이션합니다.

a.insert(0, item) #

top = a.pop() #

front = a[-1] #

왼쪽은 팀의 끝이고, 오른쪽은 팀의 우두머리다.

코드

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

class Solution:
    def findClosestLeaf(self, root: TreeNode, k: int) -> int:
        isLeaf = [False] * 1001 #  1000 
        
        from collections import defaultdict
        g = defaultdict(set)
        
        # DFS 
        def dfs(root):
            # print("...")
            if root != None and root.left == None and root.right == None:
                # print(" ...")
                isLeaf[root.val] = True
            if root.left:
                g[root.val].add(root.left.val)
                g[root.left.val].add(root.val)
                dfs(root.left)
            if root.right:
                g[root.val].add(root.right.val)
                g[root.right.val].add(root.val)
                dfs(root.right)
        #  
        dfs(root)
        
        # BFS 
        visited = { k }
        que = [k] #  
        while len(que) != 0:
            top = que.pop()
            if isLeaf[top]:
                return top
            for val in g[top]:
                if val not in visited:
                    if isLeaf[val]:
                        return val      
                    que.insert(0, val)
                    visited.add(val)
        return -1

2019.10 Update:
제1회 PAT 알고리즘 생방송 강습반 모집장, 자세한 내용 보기 클릭,
END.