Pythonでバイナリツリーから文字列を構築する

バイナリツリーがあると仮定します。文字列は、前順序トラバース方法を使用して、バイナリツリーからの括弧と整数で構成されます。 nullノードは、空の括弧のペア「（）」で表されます。また、文字列と元の二分木の間の1対1のマッピング関係に影響を与えない空の括弧のペアをすべて省略する必要があります。

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

その場合、出力は5（6（）（8））（7）

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

• ans：=空白の文字列
• 関数pot（）を定義します。これはノードを取ります、s
• nullの場合、
  • 空白の文字列を返す
• ノードの左側または右側がnullの場合、
  • return node.data
• ss：=node.data
• node.leftがnullでない場合、
  • ss：=ss concatenate'（' concatenate pot（node.left、blank string）concatenate'）'
• それ以外の場合、
  • ss：=ss concatenate'（）'
• node.rightがnullでない場合、
  • ss：=ss concatenate'（' concatenate pot（node.right、blank string）concatenate'）'
• return ss
• メインの方法から次のようにします-
• return pot（t、空白の文字列）

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

例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def insert(temp,data):
      que = []
      que.append(temp)
      while (len(que)):
         temp = que[0]
         que.pop(0)
         if (not temp.left):
            if data is not None:
               temp.left = TreeNode(data)
            else:
               temp.left = TreeNode(0)
            break
         else:
            que.append(temp.left)
         if (not temp.right):
            if data is not None:
               temp.right = TreeNode(data)
            else:
               temp.right = TreeNode(0)
            break
         else:
            que.append(temp.right)
def make_tree(elements):
   Tree = TreeNode(elements[0])
   for element in elements[1:]:
      insert(Tree, element)
   return Tree
class Solution:
   def tree2str(self, t: TreeNode):
      ans = ''
      def pot(node, s):
         if node == None or node.data == 0:
            return ''
         if node.left == node.right == None:
            return str(node.data)
         ss = str(node.data)
         if node.left != None:
            ss = ss + '(' + pot(node.left, '') + ')'
         else:
            ss = ss + '()'
         if node.right != None:
            ss = ss + '(' + pot(node.right, '') + ')'
         return ss
      return pot(t, '')
ob = Solution()
root = make_tree([5,6,7,None,8])
print(ob.tree2str(root))

入力

[5,6,7,None,8]

出力

5(6()(8))(7)