문제
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 |