題目描述
請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來(lái)序列化和反序列化二叉樹(shù)

目前創(chuàng)新互聯(lián)建站已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管、企業(yè)網(wǎng)站設(shè)計(jì)、友好網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-07 15:48
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : serializeBinaryTree.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    """
    用先序遍歷將二叉樹(shù)序列化下來(lái)，然后再反序列化即可。因?yàn)檫@里的關(guān)鍵在于如何定位到根節(jié)點(diǎn)，雖然用后
    序遍歷也可以定位根節(jié)點(diǎn)，但是在反序列化的時(shí)候就不容易實(shí)現(xiàn)。
    """
    def Serialize(self, root):
        """
        序列化的時(shí)候正常先序遍歷二叉樹(shù)即可，但是為了準(zhǔn)確定位到葉子節(jié)點(diǎn)，我們需要
        **將空節(jié)點(diǎn)也序列化下來(lái)**
        """
        def helper(pRoot, curSerial):
            if not pRoot:
                # 這里我們用'$'表示空節(jié)點(diǎn)
                curSerial.append('$')
                return

            # 用遞歸方法進(jìn)行序列化，先將根節(jié)點(diǎn)序列化，然后遍歷左子樹(shù)、右子樹(shù)
            curSerial.append(pRoot.val)
            helper(pRoot.left, curSerial)
            helper(pRoot.right, curSerial)

        if not root:
            return ''

        serialization = []
        helper(root, serialization)
        return ','.join(map(str, serialization))

    def Deserialize(self, s):
        """
        在反序列化的時(shí)候，由于構(gòu)造一個(gè)節(jié)點(diǎn)的時(shí)候默認(rèn)左右子節(jié)點(diǎn)都是空，因此如果字符串中遇到了'$'，
        可以直接忽略。也就是只需要處理非空節(jié)點(diǎn)
        """
        def helper(curStr, curRoot):
            # 遞歸出口
            if not curStr:
                return curRoot
            # 這里由于我們使用一個(gè)列表保存節(jié)點(diǎn)信息，因此可以用pop()來(lái)保存剩余待反序列化的節(jié)點(diǎn)
            curVal = curStr.pop(0)
            # 如果是'$'，即該節(jié)點(diǎn)為空，那么這時(shí)候由于輸入的curRoot也為空，直接返回即可
            if curVal != '$':
                # 從整體來(lái)看，我們需要先構(gòu)造根節(jié)點(diǎn)，然后分別構(gòu)造其左右子節(jié)點(diǎn)。
                # 遞歸在確定了出口條件之后，就只需要將整體邏輯寫(xiě)出來(lái)就行了。
                curRoot = TreeNode(int(curVal))
                curRoot.left = helper(curStr, curRoot.left)
                curRoot.right = helper(curStr, curRoot.right)

            return curRoot

        if not s:
            return None
        s = s.split(',')
        root = helper(s, None)
        return root

def printTree(root: TreeNode):
    if not root:
        return
    print(root.val)
    printTree(root.left)
    printTree(root.right)

def main():

    solution = Solution()
    root = TreeNode(10)
    root.left = TreeNode(6)
    root.right = TreeNode(14)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(8)
    root.right.left = TreeNode(12)
    root.right.right = TreeNode(16)
    s = solution.Serialize(root)
    print(s)
    printTree(solution.Deserialize(s))

if __name__ == '__main__':
    main()

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

本文題目：劍指offer：序列化二叉樹(shù)-創(chuàng)新互聯(lián)
本文地址：http://weahome.cn/article/cscidp.html