给定一个二叉树,请你求出此二叉树的最大宽度。
本题中树第 i 层的宽度定义为:第 i 层最左边的节点到最右边之间的距离,中间空节点也计入距离。
例如:
本树中第 1 层只有一个节点,故第 1 层宽度是 1 ,第二层最左侧到最右侧的距离是 2 ,所以宽度是 2 , 第三层最左侧 4 到最右侧 5 距离是 4 ,故宽度是 4,此树最大宽度是 4。
{1,2,3,4,#,4,5}
4
如题面图
{1}
1
{1,2,3,4,#,4,5,6,#,1}
5
倒数第二层的宽度为5
package main import _"fmt" import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @return int整型 */ func widthOfBinaryTree( root *TreeNode ) int { if root==nil{ return 0 } root=label(root,1) max:=1 q:=[]*TreeNode{root} for len(q)>0{ new_q:=[]*TreeNode{} for _,qi:=range q{ if qi.Left!=nil{ new_q=append(new_q,qi.Left) } if qi.Right!=nil{ new_q=append(new_q,qi.Right) } } x:=1 if len(new_q)>1{ x=new_q[len(new_q)-1].Val-new_q[0].Val+1 } if x>max{ max=x } q=new_q } return max } func label(root *TreeNode,x int)*TreeNode{ if root==nil{ return nil } root.Val=x root.Left=label(root.Left,x*2) root.Right=label(root.Right,x*2+1) return root }