[LeetCode] 513. Find Bottom Left Tree Value

문제 출처

https://leetcode.com/problems/find-bottom-left-tree-value/solutions/3384697/python3-using-deque-solution/

 

문제 풀이

• 이진 트리가 주어질 때, 트리의 가장 마지막 줄의 가장 왼쪽 값을 반환하는 함수를 작성하는 문제
  
  • 트리를 BFS처럼 순회하여 마지막 레벨을 찾고 마지막 레벨에서 가장 왼쪽 값을 찾아낸다.
  • Deque를 이용하여 루트부터 읽고 다음 레벨의 노드를 순회하며, 이때 Left 노드와 Right 노드가 있을 때 Right 노드부터 Deque에 추가해야 가장 왼쪽 값을 찾을 수 있다.

 

나의 풀이(Python3)

from collections import deque
from typing import Optional

# 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:
        deq = deque([root])

        last = None
        while deq:
            value = deq.popleft()
            last = value.val  # store popped node value

            left, right = value.left, value.right
            if right:
                deq.append(right)
            if left:
                deq.append(left)

        return last

 

Github

• https://github.com/limseunghyun95/Algorithm_study/blob/master/leetcode/find_bottom_left_tree_value.py