本篇文章給大家分享的是有關(guān)怎樣驗(yàn)證python二叉樹(shù)的前序序列化，小編覺(jué)得挺實(shí)用的，因此分享給大家學(xué)習(xí)，希望大家閱讀完這篇文章后可以有所收獲，話不多說(shuō)，跟著小編一起來(lái)看看吧。

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

一、題目?jī)?nèi)容

序列化二叉樹(shù)的一種方法是使用前序遍歷。當(dāng)我們遇到一個(gè)非空節(jié)點(diǎn)時(shí)，我們可以記錄下這個(gè)節(jié)點(diǎn)的值。如果它是一個(gè)空節(jié)點(diǎn)，我們可以使用一個(gè)標(biāo)記值記錄，例如 #。

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉樹(shù)可以被序列化為字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一個(gè)空節(jié)點(diǎn)。

給定一串以逗號(hào)分隔的序列，驗(yàn)證它是否是正確的二叉樹(shù)的前序序列化。編寫一個(gè)在不重構(gòu)樹(shù)的條件下的可行算法。

每個(gè)以逗號(hào)分隔的字符或?yàn)橐粋€(gè)整數(shù)或?yàn)橐粋€(gè)表示 null 指針的 '#' 。

你可以認(rèn)為輸入格式總是有效的，例如它永遠(yuǎn)不會(huì)包含兩個(gè)連續(xù)的逗號(hào)，比如 "1,,3" 。

示例 1:

輸入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
輸出: true

示例 2:

輸入: "1,#"
輸出: false

示例 3:

輸入: "9,#,#,1"
輸出: false

二、解題思路

用棧存儲(chǔ)數(shù)字，‘#’作為出棧的依據(jù)；

事先棧中存入一個(gè)‘#’；

當(dāng)棧中最后一個(gè)是‘#’且preorder序列最后也是‘#’，則說(shuō)明是正確的二叉樹(shù)的前序序列化；

否則若preorder中‘#’還沒(méi)有到最后位置就與棧中的‘#’匹配，則說(shuō)明是不正確的。

三、代碼

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        stack = ['#']
        i = 0
        while i < len(preorder):
            if preorder[i] == ',':
                i += 1
                continue
            elif preorder[i] == '#':
                if stack[-1] == '#':
                    if i == len(preorder) - 1:
                        stack.pop()
                    else:
                        return False
                else:
                    stack.pop()
            elif preorder[i] != '#':
                stack.append(preorder[i])
                while i < len(preorder) and preorder[i] != ',':
                    i += 1
            i += 1
        return len(stack) == 0


if __name__ == '__main__':
    s = Solution()
    preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
    ans = s.isValidSerialization(preorder)
    print(ans)

以上就是怎樣驗(yàn)證python二叉樹(shù)的前序序列化，小編相信有部分知識(shí)點(diǎn)可能是我們?nèi)粘９ぷ鲿?huì)見(jiàn)到或用到的。希望你能通過(guò)這篇文章學(xué)到更多知識(shí)。更多詳情敬請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

新聞標(biāo)題：怎樣驗(yàn)證python二叉樹(shù)的前序序列化
文章轉(zhuǎn)載：http://aaarwkj.com/article12/igcdgc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、品牌網(wǎng)站設(shè)計(jì)、動(dòng)態(tài)網(wǎng)站、外貿(mào)建站、ChatGPT、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)