Python의 BST에서 K번째 가장 작은 요소

<시간/>

이진 검색 트리가 있다고 가정합니다. BST에서 K번째로 작은 요소를 찾아야 합니다. 트리가 다음과 같다면 -

따라서 세 번째로 작은 요소를 찾으려면 k =3이고 결과는 7이 됩니다.

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

노드라고 하는 하나의 빈 목록 만들기
해결(루트, 노드) 호출
return k – 노드의 첫 번째 요소
해결 방법이 생성되고 루트 및 노드 배열이 사용되며 다음과 같이 작동합니다. -
루트가 null이면 반환
해결(루트 왼쪽, 노드)
노드 배열에 루트 값 추가
해결(루트, 노드의 오른쪽)

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

예시

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):
         temp.left = TreeNode(data)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         temp.right = TreeNode(data)
         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 kthSmallest(self, root, k):
      nodes = []
      self.solve(root,nodes)
      return nodes[k-1]
   def solve(self, root,nodes):
      if root == None:
         return
      self.solve(root.left,nodes)
      nodes.append(root.data)
      self.solve(root.right,nodes)
ob1 = Solution()
tree = make_tree([10,5,15,2,7,13])
print(ob1.kthSmallest(tree, 3))

입력

[10,5,15,2,7,13]
3

Python의 BST에서 K번째 가장 작은 요소

예시

입력

출력