二叉樹的反序列化

反序列化

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

解題思路

• 首先，應該先拿到一個序列化后數據，可能是隊列、棧、字符串(中間會有字符將其分割)，或其它形式的數據
• 當一個節點下面沒有數據的時候，我這里采用的是用null來表示的空，比如上面節點2下面沒有數據,在字符串中就用了null來表示
• 這里我將字符串轉換成了隊列的形式，當然使用字符串的形式也可以的，例如:通過split方法來分割成數組
• 創建一個隊列，把要進行處理的節點放和主到隊列里面，比如，每次循環的時候將左右分支放到這個隊列里面，因為隊列有FIFO的特性，在處理完左支的時候能夠放便的拿到右支的node
• 接下來分析代碼

TreeNode結構體

這個里面的數據很容易就看懂，val是當前節點的數據;left ,right分別保存的是左支和右支的數據

針對每個數據生成對應的TreeNode

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

這個方法主要是生成TreeNode對象的方法，上面說到當節點下面沒有子節點的時候就會用null來表不，所以這里接收到的形參如果是null的話就會反回一個空指針，相反如果不是null就會反回一個創建的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
}

這幾行代碼無非就是一個邊界條件的判斷的問題,當傳來的隊列沒有數據的時候就返回一個空,為啥是隊列?因為我將字符串轉成了隊列

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

var tempNodeQueue []*TreeNode:這里創建一個TreeNode指針數組的原因是存儲要操作節點的數據,因為我將序列化后的數據轉成了隊列,所以在這個數組中最后一個元素應該是先出來的數組,同樣第一個出來的數據是這顆二叉樹的根節點,將這個節點保存到了這個隊列里面,然后這個隊列將在下面的for循環中使用到,其余的下面再說.

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

dataQueue = dataQueue[:len(dataQueue) - 1]:因為有一個數組已經出了隊列,就要將其去掉

tempNodeQueue = append(tempNodeQueue,resultNode):經過一個判空處理,便將這個節點保存到了上面提到的隊列里面

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)
    }
}

當進入For循環后,也就證明現在這個隊列里面有數據,不管三七二十一,先將里面的數據彈出,因為只有有了數據才可以進行下面的操作(無數據,不編程)

tempNodeQueue = tempNodeQueue[1:]:因為前一行代碼將數據在這個隊列里面彈出了, 所以一行代碼是將已彈出的數據去除

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

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

可能有小伙伴存在疑問?

所返回的resultNode變量只賦值過一次,那子節點是如何賦值的呢?因為所有的TreeNode的節點我都是通過指針來處理的,

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

二叉樹的序列化

介紹

樹的序列化又是怎么一回事呢？我可以將這顆樹轉換成一定格式的數據結構，比如：轉換成一段文本可以持久化到硬盤中。

那有什么作用呢？比如Redis中的數據是在內存中的，它有一個功能是每隔一段 時間可以將數據保存到硬盤中以防止突發的斷電導至數據的丟失

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

解題思路

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

代碼

/**
序列化二叉樹
*/
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]:在隊列里面彈出一個數據

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

下面的if就是判斷當這個節點為空或者是不為空的時候需要分別怎么處理數據，上面說到如果一個節點下面沒有子節點，這里就用null來表示，所以當沒有子節點的時候就用將null添加到隊列里面

tempQueue = tempQueue[1:]:對隊列重新賦值，將彈出的那個數據去掉

tempQueue = append(tempQueue, tempNode.left):將左節點加入到隊列里面，下一行同理

運行結果