這篇文章將為大家詳細(xì)講解有關(guān)大數(shù)據(jù)中怎么驗(yàn)證二叉樹的前序序列化，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

創(chuàng)新互聯(lián)技術(shù)團(tuán)隊(duì)十年來致力于為客戶提供成都網(wǎng)站制作、成都做網(wǎng)站、成都品牌網(wǎng)站建設(shè)、網(wǎng)絡(luò)營銷推廣、搜索引擎SEO優(yōu)化等服務(wù)。經(jīng)過多年發(fā)展，公司擁有經(jīng)驗(yàn)豐富的技術(shù)團(tuán)隊(duì)，先后服務(wù)、推廣了成百上千網(wǎng)站，包括各類中小企業(yè)、企事單位、高校等機(jī)構(gòu)單位。

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

     _9_

    /   \

   3     2

  / \   / \

 4   1  #  6

/ \ / \   / \

# # # #   # #

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

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

解題思路

1，前序遍歷二叉樹的時(shí)候，如果兩個(gè)孩子是空節(jié)點(diǎn)，可以把父節(jié)點(diǎn)替換成空節(jié)點(diǎn)，依次進(jìn)行下去，如果最終只剩下根節(jié)點(diǎn)是空，則二叉樹合法

2，上述過程可以借助棧來實(shí)現(xiàn)

3，注意，由于數(shù)據(jù)可能不是個(gè)位數(shù)，所以需要用strings.Split,不能用byte直接比較

4，這個(gè)過程是邊入棧邊比較的過程

代碼實(shí)現(xiàn)

import "strings"func isValidSerialization(preorder string) bool {    nums:=strings.Split(preorder,",")    var stack []string    for i:=0;i<len(nums);i++{        stack=append(stack,nums[i])        for len(stack)>2{            l:=len(stack)            if stack[l-1]=="#" && stack[l-2]=="#" &&  stack[l-3]!="#"{//&& stack[l-3]>='0' && stack[l-3]<='9'                stack[l-3]="#"                stack=stack[:l-2]            }else{                break;            }       }    }        if len(stack)==1 && stack[0]=="#"{        return true    }    return false

關(guān)于大數(shù)據(jù)中怎么驗(yàn)證二叉樹的前序序列化就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

分享標(biāo)題：大數(shù)據(jù)中怎么驗(yàn)證二叉樹的前序序列化
文章地址：http://jinyejixie.com/article46/gpgehg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、搜索引擎優(yōu)化、手機(jī)網(wǎng)站建設(shè)、軟件開發(fā)、網(wǎng)站營銷、營銷型網(wǎng)站建設(shè)

廣告

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