Pythonの二分探索木でk番目に小さい要素を見つけるプログラム

二分探索木があり、別の整数kがあるとすると、ツリー内でk番目に小さい値を見つける必要があります。

したがって、入力が次のような場合

k =3の場合、出力は7になります

これを解決するには、次の手順に従います-

• スタック：=空のスタック

• i：=0

• ans：=-1

• スタックが空でないか、ルートがnullでない場合は、実行してください

  • ルートがnullでない場合は、実行してください

    • ルートをスタックにプッシュする

    • ルート：=ルートの左側

  • v：=スタックから要素をポップ

  • iがkと同じ場合、

    • ans：=vの値

    • ループから出てきます

  • ルート：=vの右

  • i：=i + 1

• ansを返す

理解を深めるために、次の実装を見てみましょう-

例

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

出力

7