[2024] day 60. Leetcode 513. Find Bottom Left Tree Value

gunny·2024년 2월 28일

513. Find Bottom Left Tree Value 513. Find Bottom Left Tree Value python leetcode 513. Find Bottom Left Tree Value leetcode 513. Find Bottom Left Tree Value python

코딩테스트

목록 보기

373/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 2월 28일 (수)
Leetcode daily problem

513. Find Bottom Left Tree

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem

이진 트리의 루트가 주어질 때 트리의 가장 하위 노드의 왼쪽 노드의 값을 반환한다.

Solution

Tree (binary tree), BFS

BFS(Breadth first Search) 인 너비 우선 탐색으로 트리를 탐색한다.
루트 노드에서 시작하여 각 레벨을 반복하는데,
각 수준에서 먼저 오른쪽 자식(존재하는 경우)을 추가한 다음 왼쪽 자식(존재하는 경우)을 대기열에 추가한다.
탐색이 끝날 때 마지막 노드는 트리의 마지막 행에서 가장 왼쪽 노드가 된다.

노드의 오른쪽을 먼저 추가하는 이유는 왼쪽 하위 트리부터 먼저 탐색하는 대신 오른쪽 하위 트리부터 탐색하여 가장 아래쪽의 노드가 먼저 방문되도록 해야하기 때문이다.

왼쪽부터 탐색하는 경우, 왼쪽 하위 트리를 먼저 탐색하고 그 다음에 오른쪽 하위 트리를 탐색하게 되는데, 이 경우에는 오른쪽 하위 트리의 노드가 왼쪽 하위 트리의 노드보다 먼저 방문되지 않는다.

그러나 오른쪽 하위 트리를 먼저 탐색하면, 가장 오른쪽에 있는 노드부터 탐색하게 되어 가장 마지막에 있는 왼쪽 하위 트리의 노드가 먼저 방문된다.

오른쪽 하위 트리를 먼저 탐색하여 마지막 행에서 가장 왼쪽에 있는 값을 찾기 위해서는 노드의 오른쪽으로 먼저 큐에 넣고 왼쪽을 넣는 것이다.

Code


# 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 findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        queue = [root]
        while queue:
            node = queue.pop(0)

            if node.right:
                queue.append(node.right)
            if node.left:
                queue.append(node.left)
            
        return node.val