Pythonで指定されたpostorderからバイナリ検索ツリーを構築します

ツリーを形成するには、順序付きトラバーサルも必要ですが、二分探索ツリーの場合、順序付きトラバーサルは並べ替えられた形式になります。

手順を見てみましょう-

• Inorder=ポストオーダートラバーサルのソート済みリスト。

• メソッドbuild_tree（）を定義します。これは、順序付け、順序付け後-

  を取ります。

• 順序リストが空でない場合-

  • root：=postorderの最後の値でツリーノードを作成し、その要素を削除します

  • ind：=順序リスト内のルートデータのインデックス

  • ルートの右：=build_tree（インデックスindからendまでの順序、postorder）

  • ルートの左側：=build_tree（inorder from 0 to index ind-1、postorder）

• ルートを返す

例

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

入力

[9,3,15,20,7]
[9,15,7,20,3]

出力

[3,7,9,15,20]