Leetcode 297:ツリーのシーケンス化と逆シーケンス化(超詳細な解法!!)

シーケンス化は、1つのデータ構造またはオブジェクトを連続したビットビットに変換する動作であり、さらに変換されたデータを1つのファイルまたはメモリに格納することができるとともに、ネットワークを介して別のコンピュータ環境に転送し、逆の方法で再構成して元のデータを得ることができる.
二叉木のシーケンス化と逆シーケンス化を実現するアルゴリズムを設計してください.ここでは、シーケンス/逆シーケンス化アルゴリズムの実行ロジックを限定しません.ツリーが文字列にシーケンス化され、この文字列を元のツリー構造に逆シーケンス化できることを保証する必要があります.
例:

         ：

    1
   / \
  2   3
     / \
    4   5

     "[1,2,3,null,null,4,5]"

ヒント:これはLeetCodeが現在使用している方法と一致します.詳細はLeetCodeシーケンス化ツリーのフォーマットを参照してください.このような方法を取らなければならないわけではありません.他の方法でこの問題を解決することもできます.
説明:クラスのメンバー/グローバル/静的変数を使用してステータスを格納しないでください.シーケンス化アルゴリズムと逆シーケンス化アルゴリズムはステータスがないはずです.
問題を解く構想.
まず考えられる方法は、ツリーの前シーケンス、中シーケンス、または後続の遍歴によって文字列を取得し、取得した文字列からツリーに戻ることです.
この問題の実際とLeetcode 105:前順と中順にシーケンスを遍歴して二叉木を構築する(最も詳細な解法!!)、Leetcode 106:中序と後序から配列を遍歴して二叉木を構築する(最も詳細な解法!!)同じ問題であり、2つの遍歴文字列を取得できることは明らかです.しかし、このようにするのは面倒で、私たちはもっと良い方法があります.
文字列を格納するときは、いくつかの情報を同時に格納することができます.これらの情報を通じて、1つの文字列だけで結果を得ることができます.
まず、前のシーケンス遍歴の解法を考慮して、空のノードを'#'として格納することができ、例のツリーを1 2 # # 3 4 # # 5 # #として格納することができる.では、この結果は逆シーケンス化できますか?明らかにできる.

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res = ""
        def preOrder(root):
            nonlocal res
            if not root:
                res += '# '
                return 
            res += str(root.val) + ' '
            preOrder(root.left)
            preOrder(root.right)
        preOrder(root)
        return res
            
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        datas = data.split()
        def deOrder():
            val = datas.pop(0)
            if val == '#':
                return 
            root = TreeNode(int(val))
            root.left = deOrder()
            root.right = deOrder()
            return root
        return deOrder()

次に、後続の遍歴の解法を考慮して、空のノードを'#'として格納することができ、例のツリーを# # 2 # # 4 # # 5 3 1として格納することができる.では、この結果は逆シーケンス化できますか?明らかに可能であり,ちょうど前序遍歴と対称関係である.

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        res = ""
        def postOrder(root):
            nonlocal res
            if not root:
                res += '# '
                return 
            postOrder(root.left)
            postOrder(root.right)
            res += str(root.val) + ' '
        postOrder(root)
        return res
            
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        datas = data.split()
        def deOrder():
            val = datas.pop()
            if val == '#':
                return 
            root = TreeNode(int(val))
            root.right = deOrder()
            root.left = deOrder()
            return root
        return deOrder()

では、このようなやり方は中序遍歴に依然として有効ですか?このような考え方を採用すれば,中序遍歴の結果は# 2 # 1 # 4 # 3 # 5 #である.逆シーケンス化できますか?いいえ、複数の結果が得られます.たとえば

    1
   / \
  2   4
       \
        3
         \
          5

どうしてですか.ルートノードの位置を上記のように決定することはできません.では、なぜ前順遍歴と後順遍歴が可能なのでしょうか.n # #によってnがルート(前の順序の遍歴)であると決定できるため、# # nによってnがルート(後の順序の遍歴)であり、唯一であるが、中順序の遍歴は一意ではない.
では、どうすればいいですか.実際には、ルートノードの位置を決定することが重要な問題であることが示されています.1つの解法は,右サブツリーを括弧で囲むことであり,例えばテーマの例を2 1 [ 4 3 [ 5 ] ]にシーケンス化することができる.

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        def inOrder(root):
            res = ''
            if not root:
                return ''
            l, r = inOrder(root.left), inOrder(root.right)
            if l:
                res += l + ' '
            res += str(root.val)
            if r:
                res += ' [ ' + r + ' ]'
            return res
        return inOrder(root)
            
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        datas, i = data.split(), 0
        def deOrder():
            nonlocal i
            root = None
            while i < len(datas):
                cur = datas[i]
                i += 1
                if cur == '[':
                    root.right = deOrder()
                elif cur == ']':
                    return root
                else:
                    t = TreeNode(int(cur))
                    t.left = root
                    root = t
            return root
        return deOrder()

もちろん最も簡単な実現方法は層序遍歴(≧▽≦)/ララ!!!層順遍歴は、'#'を空のノードで充填することによって実現される.

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""
        q, res = [root], ""
        while q:
            pre = q.pop(0)
            if not pre:
                res += '# '
            else:
                q.append(pre.left)
                q.append(pre.right)
                res += str(pre.val) + ' '
        return res
            
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        datas = data.split()
        root = TreeNode(int(datas.pop(0)))
        q = [root]
        while q:
            pre = q.pop(0)
            l, r = datas.pop(0), datas.pop(0)
            if l != '#':
                pre.left = TreeNode(int(l))
                q.append(pre.left)
            
            if r != '#':
                pre.right = TreeNode(int(r))
                q.append(pre.right)
        return root

reference:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/160613/C%2B%2B-Inorder-recursive-solution
この問題の他の言語バージョンをGitHub Leetcodeに追加しました
もし問題があれば、皆さんに指摘してほしい!!!