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
	//臨時保存節點的隊列
	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
}