Shulou(Shulou.com)05/31 Report--

This article mainly introduces the relevant knowledge of "how to use go language to find the maximum width of a binary tree". The editor shows you the operation process through an actual case, and the operation method is simple, fast and practical. I hope this article "how to use go language to find the maximum width of binary tree" can help you solve the problem.

Introduction

The problem is like this, there is a binary tree, let the maximum width of the Bt tree is how many nodes, but also requires the maximum width of these nodes in which layer?

For example: the following tree, its maximum width of each floor is 3, and the number of layers is on the third floor.

Process flow

This problem mainly uses queues to store nodes that need to be traversed.

At the same time, several variables are needed to store the maximum width (maxWidth), how many nodes are in each layer (count), the layer in which the maximum width is located (maxInrow), the last node in the current layer (currentRowEndNode), and the last node in the next layer (nextRowEndNode)

At the beginning of the program, the head node of the binary tree is added to the queue, and this node is assigned to the last node in the next layer because when the root node has only one node, the last node of the current line is also assigned to this node.

Traverse the queue through a loop, and when you enter the loop, you will think that you have reached a node, and count will add 1.

Start popping up the node element in the queue, and assign the child node to nextRowEndNode if its child node exists, first to the left and then to the right (because the left child node is processed first), and add these two nodes to the queue (if they exist)

It is also necessary to make a judgment on the current node to determine whether the current node has reached the last node of the current row. If so, it means that the data of the current row has been processed, and the nextRowEndNode should be assigned to currentRowEndNode,count to set 0.

Proceed to the next cycle.

Code binary tree structure type TreeNode struct {val string left * TreeNode right * TreeNode} Test code 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 ("Max width:% v Find the code func findBtMaxWidth (bt * TreeNode) (maxWidth int) for the maximum width of the binary tree in layer% v ", maxW, row)} MaxInrow int) {row: = 0 / / temporary save node's queue var tempSaveNodeQueue [] * TreeNode / / Save width 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判断里面的代码叭，为啥要分别将子节点的left、right分别赋值给nextRowEndNode呢？ 因为在一个子节点下面的left和right并不是全都存在的，有的时候会是个空，所以这里要分别赋值 if currentRowEndNode == treeNode:这一个判断里面，因为如果进入到了这个判断里面就说明到了当前层的最后一个节点了，所以就要把下一层的最后一个节点赋值给当前层的最后一个节点； 因为还有一个要找出最大宽度的一个功能，所以这个maxWidth要和coutn做一个比较如果maxWidth比较小的话就将count赋值给maxWidth，同时将当前的层数赋值给maxInrow； row:而row在这里面所充当的角色是当前是完成第几行的操作 为啥这里要定义一个currentRowEndNode和nextRowEndNode？ 这种的写法按层来处理，当获取到一个节点的时候，这时我就要拿到他们的子节点，如果现在不获取子节点的话在后面是没有办法获取的，当这一行结束的时候将nextRowEndNode赋值给currentRowEndNode，接下来nextRowEndNode再找下一层的最后一个节点。

This is the end of the content about "how to use the go language to find the maximum width of a binary tree". Thank you for your reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.