SeangG
def _(): _()
SeangG
전체 방문자
오늘
어제
  • 분류 전체보기 (37)
    • Programming Language (0)
      • Python (0)
      • Web (0)
    • Algorithm (34)
    • Art (0)
      • 3D Modeling (0)
      • Pixel (0)
      • Picture (0)
    • Game (0)
    • Project (3)
      • Problems (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Daily Question
  • Leecode
  • graph
  • next.js
  • BFS
  • react.js
  • string
  • Tree
  • spring boot
  • 로마 숫자
  • 문자열
  • Python
  • leetcode
  • github oauth
  • WSL
  • Queue
  • 매핑 테이블
  • Fast Refresh
  • dfs
  • LeedCode

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
SeangG
Algorithm

[LeetCode] 988. Smallest String Starting From Leaf (Daily Question)

[LeetCode] 988. Smallest String Starting From Leaf (Daily Question)
Algorithm

[LeetCode] 988. Smallest String Starting From Leaf (Daily Question)

2024. 4. 17. 10:51

문제


 

You are given the root of a binary tree where each node has a value in the range [0, 25] representing the letters 'a' to 'z'.

Return the lexicographically smallest string that starts at a leaf of this tree and ends at the root.

As a reminder, any shorter prefix of a string is lexicographically smaller.
    - For example, "ab" is lexicographically smaller than "aba".

A leaf of a node is a node that has no children.

 

root(트리)가 주어졌을 때 (잎노드 -> 루트노드)로 가면서 만든 문자열 중 사전적으로 가장 작은 문자열을 찾는 문제이다.

 

Example 1:
Input: root = [0,1,2,3,4,3,4]
Output: "dba"

Example 2:
Input: root = [25,1,3,1,3,0,2]
Output: "adz"

Example 3:
Input: root = [2,2,1,null,1,0,null,0]
Output: "abc"

 

풀이


아이디어

DFS로 잎노드까지 가는 모든 경로를 탐색하여 가장 작은 문자열을 찾는다.

 

코드

# 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:
    # 알파벳 테이블
    alpha = [chr(i) for i in range(ord('a'), ord('z')+1)]

    def smallestFromLeaf(self, root: Optional[TreeNode], st="") -> str:
        # 현재 노드가 존재하지 않는 경우
        if root is None: return "z"*10000

        # 문자열 추가
        st = self.alpha[root.val] + st

        # 잎노드인 경우 문자열 반환
        if root.left is None and root.right is None:
            return st

        # 자식 노드 탐색
        st1 = self.smallestFromLeaf(root.left, st)
        st2 = self.smallestFromLeaf(root.right, st)

        return min([st1, st2])

 

후기


난이도

전반적으로 쉬운 문제였다.

객체형태의 트리를 다루는데에도 익숙해져서 구현도 쉽게 할 수 있었다.

 

 

'Algorithm' 카테고리의 다른 글

[LeetCode] 200. Number of Islands (Daily Question)  (2) 2024.04.19
[LeetCode] 463. Island Perimeter (Daily Question)  (1) 2024.04.18
[LeetCode] 623. Add One Row to Tree (Daily Question)  (0) 2024.04.16
[LeetCode] 129. Sum Root to Leaf Numbers (Daily Question)  (0) 2024.04.15
[LeetCode] 404. Sum of Left Leaves (Daily Question)  (0) 2024.04.15
  • 문제
  •  
  • 풀이
  •  
  • 후기
'Algorithm' 카테고리의 다른 글
  • [LeetCode] 200. Number of Islands (Daily Question)
  • [LeetCode] 463. Island Perimeter (Daily Question)
  • [LeetCode] 623. Add One Row to Tree (Daily Question)
  • [LeetCode] 129. Sum Root to Leaf Numbers (Daily Question)
SeangG
SeangG

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.