PythonのStackを使用して、指定されたポストオーダートラバーサルからBSTを構築します

したがって、入力が[6、12、10、55、45、15]の場合、出力は

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

• 関数solve（）を定義します。これには後注文が必要です

• n：=ポストオーダーのサイズ

• root：=postorderの最後の要素で新しいツリーノードを作成します

• stk：=スタック

• ルートをstkに挿入

• i：=n-2

• i> =0の場合、実行

  • x：=値postorder [i]

    で新しいノードを作成します

  • stkが空ではなく、postorder [i]

    • temp：=stkのトップ

    • stkから最上位の要素を削除する

  • tempがnullでない場合、

    • temp.left：=x

  • それ以外の場合

    • stkトップ要素の右側：=x

  • xをstkに挿入

  • i：=i-1

• ルートを返す

• メインの方法から、次のようにします-

• リターンソルブ（ポストオーダー）

例

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

class TreeNode:
   def __init__(self, data = 0):
      self.val = data
      self.left = None
      self.right = None
def solve(postorder):
   n = len(postorder)
   root = TreeNode(postorder[n - 1])
   stk = []
   stk.append(root)
   i = n - 2
   while ( i >= 0):
      x = TreeNode(postorder[i])
      temp = None
      while (len(stk) > 0 and postorder[i] < stk[-1].val) :
         temp = stk[-1]
         stk.pop()
      if (temp != None):
         temp.left = x
      else:
         stk[-1].right = x
      stk.append(x)
      i = i - 1
   return root
def build_tree(postorder):
   return solve(postorder)
def inord( node):
   if node:
      inord(node.left)
      print( node.val, end = " ")
      inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print( "Inorder traversal:", end = " ")
inord(root)

入力

[6, 12, 10, 55, 45, 15]

出力

6 10 12 15 45 55