LeetCode 662. 二叉树的最大宽度

LeetCode 662. 二叉树的最大宽度

记录一次刷题的感悟。这道题目是我人生第一次面试的时候的手撕题目，但临场的时候面试官没有为难我，他考察的问题是求二叉树的最大宽度，但是不需要考虑 null 结点，也就是空的结点不计入宽度当中。

当我再次刷到这道题，发现当初面试的时候自己的理解有问题，计算宽度的时候应该考虑 null 结点，比如对于下面这样一棵树：

这棵树的最大宽度就是 7，而不是 2。

有了这一层限制，这道题目就具有了一定的难度，下面开始分析解这道题的思路。

题目描述

思路

我们使用 BFS 来解这道问题。

其实从后验的角度来说，这道题目没有什么难度，但是难就难在临场想不到这道题的正确思路。

正确的思路其实是，新开一个数据结构，同时保存二叉树的结点以及当前节点的编号。每一次计算一层的最大的宽度时，计算队列头和队列尾两个二叉树结点之间编号的差值。

二叉树结点的编号计算规则如下：对于当前的结点$i$，它的左孩子结点编号为$2\times i$，右孩子结点编号为$2\times i+1$。基于二叉树结点的编号，我们甚至可以在一个数组当中存储二叉树。堆排序正是利用了这条性质，在数组当中利用二叉树建堆来实现最大堆或最小堆。

Golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type pair struct {
    node  *TreeNode
    index int
}

func widthOfBinaryTree(root *TreeNode) int {
    ans := 1
    q := []pair{}
    q = append(q, pair{root, 1})
    for len(q) > 0 {
        ans = max(ans, q[len(q) - 1].index -  q[0].index + 1)
        currLen := len(q)
        for i := 0; i < currLen; i ++ {
            p := q[0]; q = q[1:]
            if p.node.Left != nil {
                q = append(q, pair{p.node.Left, 2 * p.index})
            }
            if p.node.Right != nil {
                q = append(q, pair{p.node.Right, 2 * p.index + 1})
            }
        }
    }
    return ans
}