Python의 이진 검색 트리에서 k 번째로 작은 요소를 찾는 프로그램

<시간/>

이진 검색 트리가 있고 또 다른 정수 k가 트리에서 k번째로 작은 값을 찾아야 한다고 가정합니다.

따라서 입력이 다음과 같으면

k =3이면 출력은 7이 됩니다.

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

스택 :=빈 스택
나는 :=0
as :=-1
스택이 비어 있지 않거나 루트가 null이 아닌 동안 수행
- 루트가 null이 아닌 동안 수행
  - 스택에 루트 푸시
  - root :=root의 왼쪽
- v :=스택에서 요소 팝
- i가 k와 같으면
  - as :=v의 값
  - 루프에서 나오다
- root :=v의 오른쪽
- 나는 :=나는 + 1
반환

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

예시

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None

class Solution:
   def solve(self, root, k):
      stack = []
      i = 0
      ans = -1
      while stack or root:
         while root:
            stack.append(root)
               root = root.left
         v = stack.pop()
         if i == k:
            ans = v.val
            break
         root = v.right
         i += 1
      return ans
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root, 3))

입력

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
3