PythonでO（n）時間とO（1）空間でBSTの中央値を見つける

二分探索木（BST）があるとすると、その中央値を見つける必要があります。偶数のノードの場合、中央値=（（n / 2番目のノード+（n + 1）/ 2番目のノード）/ 2奇数のノードの場合、中央値=（n + 1）/2番目のノードです。

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

その場合、出力は7になります

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

• rootがNoneと同じ場合、

  • 0を返す

• node_count：=ツリー内のノードの数

• count_curr：=0

• 現在：=ルート

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

  • current.left nullの場合、

    • count_curr：=count_curr + 1

    • node_count mod 2が0でなく、count_currが（node_count + 1）/ 2と同じである場合、

      • previous.dataを返す

    • それ以外の場合、node_count mod 2が0で、count_currが（node_count / 2）+1と同じである場合、

      • return（previous.data + current.data）/ 2

    • 前：=現在

    • current：=current.right

  • それ以外の場合

    • 前：=current.left

    • previous.rightはnullではなく、previous.rightはcurrentと同じではありませんが、実行してください

      • previous：=previous.right

    • previous.rightがnullの場合、

      • previous.right：=current

      • current：=current.left

    • それ以外の場合

      • previous.right：=なし

      • 前：=前

      • count_curr：=count_curr + 1

      • node_count mod 2が0でなく、count_currが（node_count + 1）/ 2と同じである場合、

        • current.dataを返す

      • それ以外の場合、node_count mod 2が0で、count_currが（node_count / 2）+ 1と同じである場合、

        • return（previous.data + current.data）/ 2

      • 前：=現在

      • current：=current.right

例

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

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
def number_of_nodes(root):
   node_count = 0
   if (root == None):
      return node_count
   current = root
   while (current != None):
      if (current.left == None):
         node_count+=1
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if(previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            node_count += 1
            current = current.right
   return node_count
def calculate_median(root):
   if (root == None):
      return 0
   node_count = number_of_nodes(root)
   count_curr = 0
   current = root
   while (current != None):
      if (current.left == None):
         count_curr += 1
         if (node_count % 2 != 0 and count_curr == (node_count + 1)//2):
            return previous.data
         elif (node_count % 2 == 0 and count_curr == (node_count//2)+1):
            return (previous.data + current.data)//2
         previous = current
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if (previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            previous = previous
            count_curr+= 1
            if (node_count % 2 != 0 and count_curr == (node_count + 1) // 2 ):
               return current.data
            elif (node_count%2 == 0 and count_curr == (node_count // 2) + 1):
               return (previous.data+current.data)//2
            previous = current
            current = current.right
root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)
print(calculate_median(root))

入力

root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)

出力

7