Python의 잎에서 시작하는 가장 작은 문자열

이진 트리의 루트가 있다고 가정하고 각 노드에는 0에서 25 사이의 값이 포함되어 있으며 이 값은 'a'에서 'z'까지의 문자를 나타냅니다. 값 0은 'a'를 나타내고 값 1은 'b'를 나타냅니다. ', 등등. 우리는 이 트리의 잎에서 시작하여 루트에서 끝나는 사전식으로 가장 작은 문자열을 검색해야 합니다. 트리가 다음과 같다면 -

그런 다음 시퀀스가 ​​[0,3,25]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 다음과 같이 dfs 순회 방법을 정의합니다.

• 노드가 null이 아니면

  • 노드 값을 A에 문자로 삽입

  • 노드에 왼쪽 및 오른쪽 자식이 없으면

    • ans :=역 형식의 문자열인 ans 및 A 요소의 최소값

    • A에서 마지막 요소 삭제

    • 반환

  • 수행 dfs(노드의 왼쪽, A)

  • 수행 dfs(노드의 오른쪽, A)

  • A에서 마지막 요소 삭제

  • 반환

• 실제 방법은 다음과 같습니다 -

• as :="~"

• 호출 dfs(root, A로 빈 배열)

• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         break
      else:
         que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution(object):
   def smallestFromLeaf(self, root):
      self.ans = "~"
      self.dfs(root,[])
      return self.ans
   def dfs(self, node, A):
      if node:
         A.append(chr(node.data + ord('a')))
         if not node.left and not node.right:
            self.ans = min(self.ans, ''.join(reversed(A)))
            A.pop()
            return
      self.dfs(node.left,A)
      self.dfs(node.right,A)
      A.pop()
      return
root = make_tree([25,1,3,1,3,0,2])
ob = Solution()
print(ob.smallestFromLeaf(root))

입력

[25,1,3,1,3,0,2]

출력

adz