怎么利用go語言實現(xiàn)查找二叉樹中的最大寬度

這篇文章主要介紹“怎么利用go語言實現(xiàn)查找二叉樹中的最大寬度”的相關(guān)知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強(qiáng)，希望這篇“怎么利用go語言實現(xiàn)查找二叉樹中的最大寬度”文章能幫助大家解決問題。

介紹

這道題是這樣的，有一個二叉樹，讓求出這顆Bt樹里面最大的寬度是有幾個節(jié)點(diǎn)，同時還要求出最大寬度的這些節(jié)點(diǎn)在第幾層？

比如:下面這顆樹，它每層最大的寬度是3，所在的層數(shù)是在第3層

流程

• 這個題主要是使用隊列的方式來存儲需要遍歷的節(jié)點(diǎn)

• 同時還需要幾個變量來存儲最大的寬度(maxWidth)、每層有幾個節(jié)點(diǎn)(count)、最大寬度所在的層(maxInrow)、當(dāng)前層最后一個節(jié)點(diǎn)(currentRowEndNode)、下一層最后一個節(jié)點(diǎn)(nextRowEndNode)

• 程序的一開始，便將二叉樹的頭節(jié)點(diǎn)加入到隊列里面，同時將這個節(jié)點(diǎn)賦值給下一層最后一個節(jié)點(diǎn)因當(dāng)根節(jié)點(diǎn)只有一個節(jié)點(diǎn)，同時也將當(dāng)前行的最后一個節(jié)點(diǎn)賦值為這個節(jié)點(diǎn)

• 通過循環(huán)來對這個隊列進(jìn)行遍歷，當(dāng)進(jìn)入循環(huán)后就認(rèn)為走到了一個節(jié)點(diǎn)，count就要加1

• 將隊列里面的節(jié)點(diǎn)元素開始彈出，如果它的子節(jié)點(diǎn)存在就將子節(jié)點(diǎn)賦值給nextRowEndNode,先賦值左再賦值右(因為先處理的是左子節(jié)點(diǎn))，同時將這倆個節(jié)點(diǎn)加入到隊列里面(如果它們存在的話)

• 還要對當(dāng)前的節(jié)點(diǎn)進(jìn)行一個判斷，判斷當(dāng)前的節(jié)點(diǎn)是不是到了當(dāng)前行的最后一個節(jié)點(diǎn)，如果是的話，就代表當(dāng)前行的數(shù)據(jù)已經(jīng)處理完成，就要把nextRowEndNode賦值給currentRowEndNode，count置0

• 進(jìn)行下一波循環(huán)

代碼

二叉樹結(jié)構(gòu)體

type TreeNode struct {
	val   string
	left  *TreeNode
	right *TreeNode
}

測試代碼

func main() {
	sNode := &TreeNode{val: "1"}
	sNode.left = &TreeNode{val: "2"}
	sNode.right = &TreeNode{val: "3"}
	sNode.left.left = &TreeNode{val: "4"}
	sNode.left.right = &TreeNode{val: "5"}
	sNode.right.left = &TreeNode{val: "6"}
	sNode.left.left.left = &TreeNode{val: "7"}
	sNode.left.left.right = &TreeNode{val: "8"}
	sNode.left.right.left = &TreeNode{val: "9"}
	sNode.left.right.right = &TreeNode{val: "10"}
	sNode.right.left.left = &TreeNode{val: "11"}
	maxW, row := findBtMaxWidth(sNode)
	fmt.Printf("最大寬度: %v;在第 %v層", maxW, row)
}

查找二叉樹最大寬度的代碼

func findBtMaxWidth(bt *TreeNode) (maxWidth int, maxInrow int) {
	row := 0
	//臨時保存節(jié)點(diǎn)的隊列
	var tempSaveNodeQueue []*TreeNode
	//保存寬度
	count := 1
	var currentRowEndNode *TreeNode
	var nextRowEndNode *TreeNode
	if bt != nil {
		nextRowEndNode = bt
		currentRowEndNode = nextRowEndNode
		tempSaveNodeQueue = append(tempSaveNodeQueue, bt)
	}
	for len(tempSaveNodeQueue) != 0 {
		count++
		treeNode := tempSaveNodeQueue[0]
		tempSaveNodeQueue = tempSaveNodeQueue[1:]

		if treeNode.left != nil {
			nextRowEndNode = treeNode.left
			tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.left)
		}

		if treeNode.right != nil {
			nextRowEndNode = treeNode.right
			tempSaveNodeQueue = append(tempSaveNodeQueue, treeNode.right)
		}
		if currentRowEndNode == treeNode {
			row++
			currentRowEndNode = nextRowEndNode
			if maxWidth < count {
				maxInrow = row
				maxWidth = count
			}
			count = 0
		}
	}
	return
}

代碼解讀

這里面的代碼大部分的邏輯還是很簡單的，

說一下在if判斷里面的代碼叭，為啥要分別將子節(jié)點(diǎn)的left、right分別賦值給nextRowEndNode呢？

因為在一個子節(jié)點(diǎn)下面的left和right并不是全都存在的，有的時候會是個空，所以這里要分別賦值

if currentRowEndNode == treeNode:這一個判斷里面，因為如果進(jìn)入到了這個判斷里面就說明到了當(dāng)前層的最后一個節(jié)點(diǎn)了，所以就要把下一層的最后一個節(jié)點(diǎn)賦值給當(dāng)前層的最后一個節(jié)點(diǎn)；

因為還有一個要找出最大寬度的一個功能，所以這個maxWidth要和coutn做一個比較如果maxWidth比較小的話就將count賦值給maxWidth，同時將當(dāng)前的層數(shù)賦值給maxInrow；

row:而row在這里面所充當(dāng)?shù)慕巧钱?dāng)前是完成第幾行的操作

為啥這里要定義一個currentRowEndNode和nextRowEndNode？

這種的寫法按層來處理，當(dāng)獲取到一個節(jié)點(diǎn)的時候，這時我就要拿到他們的子節(jié)點(diǎn)，如果現(xiàn)在不獲取子節(jié)點(diǎn)的話在后面是沒有辦法獲取的，當(dāng)這一行結(jié)束的時候?qū)extRowEndNode賦值給currentRowEndNode，接下來nextRowEndNode再找下一層的最后一個節(jié)點(diǎn)。

關(guān)于“怎么利用go語言實現(xiàn)查找二叉樹中的最大寬度”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。