Pythonでプレオーダーおよびポストオーダートラバーサルからバイナリツリーを構築する

PreorderとPostorderの2つのトラバーサルシーケンスがあるとすると、これら2つのシーケンスからバイナリツリーを生成する必要があります。したがって、シーケンスが[1,2,4,5,3,6,7]、[4,5,2,6,7,3,1]の場合、出力は

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

• ans：=値pre [0]を取得してツリーノードを作成し、スタック：=空のスタックを作成し、ansを挿入します
• i：=1およびj：=0
• whilei<前の長さとj<後の長さ
  • スタックの最上位値=post[j]の場合、jを1増やし、スタックからポップして、次の反復に進みます
  • node：=値pre [i]
  でツリーノードを作成します
  • スタックトップノードの左側が空の場合は、スタックトップノードの左側をノードとして設定します。それ以外の場合は、スタックトップノードの右側をノードとして設定します。
  • ノードをスタックに挿入
  • iを1増やします
• 回答を返す

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

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def height(root):
   if root is None:
      return 0
   else :
      # Compute the height of left and right subtree
      l_height = height(root.left)
      r_height = height(root.right)
      #Find the greater one, and return it
      if l_height > r_height :
         return l_height+1
      else:
         return r_height+1
def print_given_level(root, level):
   if root is None:
      return
   if level == 1:
      print(root.data,end = ',')
   elif level > 1 :
      print_given_level(root.left , level-1)
      print_given_level(root.right , level-1)
def level_order(root):
   print('[', end = '')
   h = height(root)
   for i in range(1, h+1):
      print_given_level(root, i)
   print(']')
class Solution(object):
   def constructFromPrePost(self, pre, post):
      """
      :type pre: List[int]
      :type post: List[int]
      :rtype: TreeNode
      """
      ans = TreeNode(pre[0])
      stack = [ans]
      i = 1
      j = 0
      while i < len(pre) and j < len(post):
         if stack[-1].data == post[j]:
            j+=1
            stack.pop(-1)
            continue
         node = TreeNode(pre[i])
         if not stack[-1].left:
            stack[-1].left = node
         else:
            stack[-1].right = node
            stack.append(node)
            i+=1
   return ans
ob = Solution()
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]
tree = ob.constructFromPrePost(pre, post)
level_order(tree)

入力

[1,2,4,5,3,6,7]
[4,5,2,6,7,3,1]
pre = [1,2,4,5,3,6,7]
post = [4,5,2,6,7,3,1]

出力

[1,2,3,4,5,6,7,]