二叉樹的反序列化

反序列化

樹的反序列化故名知意就是將一個序列化成字符串或者其它形式的數(shù)據(jù)重新的生成一顆二叉樹,如下這顆二叉樹將它序列化成字符串后的結(jié)果[5,4,null,null,3,2,1],而現(xiàn)在要做的是要將這個字符串重新的生成一顆二叉樹(生成下面這顆樹，因?yàn)檫@個字符串就是通過這顆樹序列化來的)。

解題思路

• 首先，應(yīng)該先拿到一個序列化后數(shù)據(jù)，可能是隊(duì)列、棧、字符串(中間會有字符將其分割)，或其它形式的數(shù)據(jù)
• 當(dāng)一個節(jié)點(diǎn)下面沒有數(shù)據(jù)的時候，我這里采用的是用null來表示的空，比如上面節(jié)點(diǎn)2下面沒有數(shù)據(jù),在字符串中就用了null來表示
• 這里我將字符串轉(zhuǎn)換成了隊(duì)列的形式，當(dāng)然使用字符串的形式也可以的，例如:通過split方法來分割成數(shù)組
• 創(chuàng)建一個隊(duì)列，把要進(jìn)行處理的節(jié)點(diǎn)放和主到隊(duì)列里面，比如，每次循環(huán)的時候?qū)⒆笥曳种Х诺竭@個隊(duì)列里面，因?yàn)殛?duì)列有FIFO的特性，在處理完左支的時候能夠放便的拿到右支的node
• 接下來分析代碼

TreeNode結(jié)構(gòu)體

這個里面的數(shù)據(jù)很容易就看懂，val是當(dāng)前節(jié)點(diǎn)的數(shù)據(jù);left ,right分別保存的是左支和右支的數(shù)據(jù)

針對每個數(shù)據(jù)生成對應(yīng)的TreeNode

func GenerateNode(str string) *TreeNode {
	if str == "null" {
		return nil
	}
	return &TreeNode{val: str}
}

這個方法主要是生成TreeNode對象的方法，上面說到當(dāng)節(jié)點(diǎn)下面沒有子節(jié)點(diǎn)的時候就會用null來表不，所以這里接收到的形參如果是null的話就會反回一個空指針，相反如果不是null就會反回一個創(chuàng)建的TreeNode對象，并將val屬性賦值

反序列化方法

func DeserializationTb(dataQueue []string) (resultNode *TreeNode) {
	if len(dataQueue) == 0 {
		return nil
	}
	var tempNodeQueue []*TreeNode
	resultNode = generateNode(dataQueue[len(dataQueue) - 1])
	dataQueue = dataQueue[:len(dataQueue) - 1]
	if resultNode != nil {
		tempNodeQueue = append(tempNodeQueue,resultNode)
	}
	var tempNode *TreeNode
	for len(tempNodeQueue) != 0 {
		tempNode = tempNodeQueue[0]
		tempNodeQueue = tempNodeQueue[1:]
		if len(dataQueue) > 0 {
			tempNode.left = generateNode(dataQueue[len(dataQueue) - 1])
			dataQueue = dataQueue[:len(dataQueue) - 1]
			tempNode.right = generateNode(dataQueue[len(dataQueue) - 1])
			dataQueue = dataQueue[:len(dataQueue) - 1]
		}
		if tempNode.left != nil {
			tempNodeQueue = append(tempNodeQueue,tempNode.left)
		}
		if tempNode.right != nil {
			tempNodeQueue = append(tempNodeQueue,tempNode.right)
		}
	}
	return
}

代碼解讀

這個方法的代碼比較多，這里就會塊來說一下:

if len(dataQueue) == 0 {
		return nil
}

這幾行代碼無非就是一個邊界條件的判斷的問題,當(dāng)傳來的隊(duì)列沒有數(shù)據(jù)的時候就返回一個空,為啥是隊(duì)列?因?yàn)槲覍⒆址D(zhuǎn)成了隊(duì)列

var tempNodeQueue []*TreeNode
resultNode = generateNode(dataQueue[len(dataQueue) - 1])
dataQueue = dataQueue[:len(dataQueue) - 1]
if resultNode != nil {
	tempNodeQueue = append(tempNodeQueue,resultNode)
}

var tempNodeQueue []*TreeNode:這里創(chuàng)建一個TreeNode指針數(shù)組的原因是存儲要操作節(jié)點(diǎn)的數(shù)據(jù),因?yàn)槲覍⑿蛄谢蟮臄?shù)據(jù)轉(zhuǎn)成了隊(duì)列,所以在這個數(shù)組中最后一個元素應(yīng)該是先出來的數(shù)組,同樣第一個出來的數(shù)據(jù)是這顆二叉樹的根節(jié)點(diǎn),將這個節(jié)點(diǎn)保存到了這個隊(duì)列里面,然后這個隊(duì)列將在下面的for循環(huán)中使用到,其余的下面再說.

resultNode = generateNode(dataQueue[len(dataQueue) - 1]):這里便是將出隊(duì)列,并通過generateNode生成一個TreeNode對象

dataQueue = dataQueue[:len(dataQueue) - 1]:因?yàn)橛幸粋€數(shù)組已經(jīng)出了隊(duì)列,就要將其去掉

tempNodeQueue = append(tempNodeQueue,resultNode):經(jīng)過一個判空處理,便將這個節(jié)點(diǎn)保存到了上面提到的隊(duì)列里面

for len(tempNodeQueue) != 0 {
    tempNode = tempNodeQueue[0]
    tempNodeQueue = tempNodeQueue[1:]
    if len(dataQueue) > 0 {
        tempNode.left = generateNode(dataQueue[len(dataQueue) - 1])
        dataQueue = dataQueue[:len(dataQueue) - 1]
        tempNode.right = generateNode(dataQueue[len(dataQueue) - 1])
        dataQueue = dataQueue[:len(dataQueue) - 1]
    }
    if tempNode.left != nil {
        tempNodeQueue = append(tempNodeQueue,tempNode.left)
    }
    if tempNode.right != nil {
        tempNodeQueue = append(tempNodeQueue,tempNode.right)
    }
}

當(dāng)進(jìn)入For循環(huán)后,也就證明現(xiàn)在這個隊(duì)列里面有數(shù)據(jù),不管三七二十一,先將里面的數(shù)據(jù)彈出,因?yàn)橹挥杏辛藬?shù)據(jù)才可以進(jìn)行下面的操作(無數(shù)據(jù),不編程)

tempNodeQueue = tempNodeQueue[1:]:因?yàn)榍耙恍写a將數(shù)據(jù)在這個隊(duì)列里面彈出了, 所以一行代碼是將已彈出的數(shù)據(jù)去除

tempNode.left = generateNode(dataQueue[len(dataQueue) - 1]):當(dāng)傳來序列化二叉樹的存在數(shù)據(jù)的時候就將其節(jié)點(diǎn)的left , right分支進(jìn)么賦值,下一行代碼就是將彈出的數(shù)據(jù)去除,接下來的兩行便是對right節(jié)點(diǎn)的處理,同left一樣

tempNodeQueue = append(tempNodeQueue,tempNode.left):如果tempNode的左節(jié)點(diǎn)存在的時候就將其保存到隊(duì)列中,遍歷tempNodeQueue隊(duì)列,再次執(zhí)行上面的步驟.

可能有小伙伴存在疑問?

所返回的resultNode變量只賦值過一次,那子節(jié)點(diǎn)是如何賦值的呢?因?yàn)樗械腡reeNode的節(jié)點(diǎn)我都是通過指針來處理的,

而在For里面的第一行代碼所彈出的數(shù)據(jù)指向的地址正是resultNode的地址,所以在生成完樹之后,我只要抓住這顆樹的根節(jié)點(diǎn)就好了

二叉樹的序列化

介紹

樹的序列化又是怎么一回事呢？我可以將這顆樹轉(zhuǎn)換成一定格式的數(shù)據(jù)結(jié)構(gòu)，比如：轉(zhuǎn)換成一段文本可以持久化到硬盤中。

那有什么作用呢？比如Redis中的數(shù)據(jù)是在內(nèi)存中的，它有一個功能是每隔一段 時間可以將數(shù)據(jù)保存到硬盤中以防止突發(fā)的斷電導(dǎo)至數(shù)據(jù)的丟失

這里說的樹的序列化你也可以這樣的理解，我要將一顆二叉樹里面的數(shù)據(jù)序列化保存到硬盤，以便下次使用這里面的數(shù)的據(jù)的時候可以直接生成這顆樹

解題思路

• 參于解這種題，想到的是通過對二叉樹的按層來遍歷來解決，當(dāng)一個節(jié)點(diǎn)沒有子節(jié)點(diǎn)的時候，將其視為空， 我這里用null來表示的
• 在這個里面序列化時我是先處理的左子節(jié)點(diǎn)，然后在處理右子節(jié)點(diǎn)
• 同反序列化一樣，暫存數(shù)據(jù)的結(jié)構(gòu)我使用的是隊(duì)列的方式，還需要將獲得的數(shù)據(jù)也要保存到一個隊(duì)列里面
• 在程序的開始如果所給的頭節(jié)點(diǎn)不為空，就將頭節(jié)點(diǎn)加入到隊(duì)列
• 在對隊(duì)列遍歷的時候彈出隊(duì)列里面的數(shù)據(jù)(注:隊(duì)列有FIFO的特性)，將本節(jié)點(diǎn)的val放到保存數(shù)據(jù)的隊(duì)列里面
• 依次將本節(jié)點(diǎn)的左子節(jié)點(diǎn)和右子節(jié)點(diǎn)放到隊(duì)列里面，在次執(zhí)行上述步驟

代碼

/**
序列化二叉樹
*/
func SerializationTb(bt *TreeNode) (saveSerData []string) {
	root := bt
	var tempQueue []*TreeNode
	if root != nil {
		tempQueue = append(tempQueue, root)
	}
	var tempNode *TreeNode
	for len(tempQueue) != 0 {
		tempNode = tempQueue[0]
		if tempNode != nil {
			saveSerData = append(saveSerData, tempNode.val)
		} else {
			saveSerData = append(saveSerData, "null")
		}
		tempQueue = tempQueue[1:]
		if tempNode != nil {
			tempQueue = append(tempQueue, tempNode.left)
			tempQueue = append(tempQueue, tempNode.right)
		}
	}
	return
}

代碼解讀

這些代碼還是很好看懂的，這里就說下for里面的代碼吧~~

tempNode = tempQueue[0]:在隊(duì)列里面彈出一個數(shù)據(jù)

saveSerData = append(saveSerData, tempNode.val):將tempNode的val屬性保存到saveSerData隊(duì)列里面

下面的if就是判斷當(dāng)這個節(jié)點(diǎn)為空或者是不為空的時候需要分別怎么處理數(shù)據(jù)，上面說到如果一個節(jié)點(diǎn)下面沒有子節(jié)點(diǎn)，這里就用null來表示，所以當(dāng)沒有子節(jié)點(diǎn)的時候就用將null添加到隊(duì)列里面

tempQueue = tempQueue[1:]:對隊(duì)列重新賦值，將彈出的那個數(shù)據(jù)去掉

tempQueue = append(tempQueue, tempNode.left):將左節(jié)點(diǎn)加入到隊(duì)列里面，下一行同理

運(yùn)行結(jié)果