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

第利用go語言實現(xiàn)查找二叉樹中的最大寬度目錄介紹流程代碼二叉樹結構體測試代碼查找二叉樹最大寬度的代碼代碼解讀

介紹

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

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

流程

這個題主要是使用隊列的方式來存儲需要遍歷的節(jié)點同時還需要幾個變量來存儲最大的寬度(maxWidth)、每層有幾個節(jié)點(count)、最大寬度所在的層(maxInrow)、當前層最后一個節(jié)點(currentRowEndNode)、下一層最后一個節(jié)點(nextRowEndNode)程序的一開始，便將二叉樹的頭節(jié)點加入到隊列里面，同時將這個節(jié)點賦值給下一層最后一個節(jié)點因當根節(jié)點只有一個節(jié)點，同時也將當前行的最后一個節(jié)點賦值為這個節(jié)點通過循環(huán)來對這個隊列進行遍歷，當進入循環(huán)后就認為走到了一個節(jié)點，count就要加1將隊列里面的節(jié)點元素開始彈出，如果它的子節(jié)點存在就將子節(jié)點賦值給nextRowEndNode,先賦值左再賦值右(因為先處理的是左子節(jié)點)，同時將這倆個節(jié)點加入到隊列里面(如果它們存在的話)還要對當前的節(jié)點進行一個判斷，判斷當前的節(jié)點是不是到了當前行的最后一個節(jié)點，如果是的話，就代表當前行的數據已經處理完成，就要把nextRowEndNode賦值給currentRowEndNode，count置0進行下一波循環(huán)

代碼

二叉樹結構體

typeTreeNodestruct{

valstring

left*TreeNode

right*TreeNode

}

測試代碼

funcmain(){

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)

}

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

funcfindBtMaxWidth(bt*TreeNode)(maxWidthint,maxInrowint){

row:=0

//臨時保存節(jié)點的隊列

vartempSaveNodeQueue[]*TreeNode

//保存寬度

count:=1

varcurrentRowEndNode*TreeNode

varnextRowEndNode*TreeNode

ifbt!=nil{

nextRowEndNode=bt

currentRowEndNode=nextRowEndNode

tempSaveNodeQueue=append(tempSaveNodeQueue,bt)

forlen(tempSaveNodeQueue)!=0{

count++

treeNode:=tempSaveNodeQueue[0]

tempSaveNodeQueue=tempSaveNodeQueue[1:]

iftreeNode.left!=nil{

nextRowEndNode=treeNode.left

tempSaveNodeQueue=append(tempSaveNodeQueue,treeNode.left)

iftreeNode.right!=nil{

nextRowEndNode=treeNode.right

tempSaveNodeQueue=append(tempSaveNodeQueue,treeNode.right)

ifcurrentRowEndNode==treeNode{

row++

currentRowEndNode=nextRowEndNode

ifmaxWidthcount{

maxInrow=row

maxWidth=count

count=0

return

}

代碼解讀

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

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

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

ifcurrentRowEndNode==treeNode:這一個判斷里面，因為如果進入到了這個判斷里面就說明到了當前層的最后一個節(jié)點了，所以就要把下一層的最后一個節(jié)點賦值給當前層的最后一個節(jié)點；

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

row:而row在這里面所充當的角色是當前是完成第幾行的操作

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