Pythonでインオーダートラバーサルとポストオーダートラバーサルからバイナリツリーを構築する

二分木のインオーダーおよびポストオーダートラバーサルシーケンスがあるとします。これらのシーケンスからツリーを生成する必要があります。したがって、事後順序と順序順のシーケンスが[9,15,7,20,3]と[9,3,15,20,7]の場合、ツリーは-

手順を見てみましょう-

• メソッドがビルドツリーと呼ばれ、プレオーダーリストとインオーダーリストがあるとします
• root：=ポストオーダーから最後のノード、ポストオーダーから最初のノードを削除
• root_index：=インオーダーリストからのroot.valのインデックス
• leftまたはroot：=buildTree（root_index + 1からendまでの順序のサブセット、postorder）
• rightまたはroot：=buildTree（インデックス0からroot_indexへの順序のサブセット、事後順序）

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

例

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

入力

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

出力

9, 15, 7, 20, 3,