662_maximum_width_of_binary_tree

662. 二叉树最大宽度 中等

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。

示例 1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

示例 2:

输入: 

          1
         /  
        3    
       / \       
      5   3     

输出: 2
解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。

示例 3:

输入: 

          1
         / \
        3   2 
       /        
      5      

输出: 2
解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。

示例 4:

输入: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
输出: 8
解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。

注意: 答案在32位有符号整数的表示范围内。

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{
        Val:   1,
        Left:  &TreeNode{Val: 2},
        Right: &TreeNode{Val: 3},
    }
    fmt.Println(widthOfBinaryTree(root)) // 2
}

// 满二叉树的节点宽度性质
//         1
//    2          3
//  4   5      6   7
// 8 9 10 11 12 13 14 15

// 理解宽度：最右边与最左边的数值之差
func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var width int
    q := []*TreeNode{root}
    for len(q) > 0 {
        counts := len(q)
        width = max(width, q[len(q)-1].Val-q[0].Val+1) // 宽度为差值加 1
        for i := 0; i < counts; i++ {
            cur := q[0]
            q = q[1:]
            if cur.Left != nil {
                cur.Left.Val = cur.Val * 2
                q = append(q, cur.Left)
            }
            if cur.Right != nil {
                cur.Right.Val = cur.Val*2 + 1
                q = append(q, cur.Right)
            }
        }
    }
    return width
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}