C练题笔记之：Leetcode-662. 二叉树最大宽度

题目：
 

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在  32 位 带符号整数范围内。

示例 1：

输入：root = [1,3,2,5,3,null,9]
输出：4
解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：

输入：root = [1,3,2,5,null,null,9,6,null,7]
输出：7
解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：

输入：root = [1,3,2,5]
输出：2
解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。

提示：

树中节点的数目范围是 [1, 3000]
-100 <= Node.val <= 100

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-width-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

结果：

 

解题思路：

这题做了挺久，最后想到的还是标记。一开始卡在了标记超出范围了。

首先很low的搞了个全局变量hashMap，因为题目说明做多3000，所以范围定在了30001（下标从1开始做记录）。里面的第一个元素，用来存储当前层级上最左边的数值。第二个元素存储当前该层级上最大宽度。

每一层的处理：

        每一层都从1开始重新计数，因为递归传下了上一层为止的总节点数和上一层的节点数，因此很容易计算出当前的这一层第一个数。

        递归参数：

                root：当前节点

                beforeSum：上一层为止所有节点数之和。

                beforNCount：上一层的所有节点数。

                n：当前层数

                index：当前节点标记

        节点标记：当前为index，左子节点为 index * 2 ，右子节点为：index * 2 + 1；

        层数：当前为n， 下一层就是 n + 1

        通过inde可以获得当前节点是本层的第几个： index - sum即可获得。（只记录最小的到hashMap[ i ] [ 0 ] 中）

        当前层的最大节点数 = beforeNCount * 2。

另：需要如果一开始循环全部是右节点，着中国情况下，为了节省index的计算，直接让忽略同一层只有一个的节点。

最后循环hashMap，去除hashMap[ i ] [ 1 ] 处最大的返回就好了。

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
unsigned int hashMap[3001][2] = {0}; //[min, count]的方式存储每一层最小编号（每一层都从1开始）1和当前层次中的最大宽度
 
void DfxGetHashMap(struct TreeNode* root, unsigned long long sum, unsigned long long nCount, int n, unsigned long long index)
{
    if (root == NULL) {
        return;
    }
    //printf("root->val = %d\n", root->val);
    if (hashMap[n][0] == 0) {
        hashMap[n][0] = index - sum;
        hashMap[n][1] = 1;
    } else {
        hashMap[n][1] = index - sum - hashMap[n][0] + 1;
    }
    DfxGetHashMap(root->left, sum + 2 * nCount, nCount * 2, n + 1, index * 2);
    DfxGetHashMap(root->right, sum + 2 * nCount, nCount * 2, n + 1, index * 2 + 1);
}
int widthOfBinaryTree(struct TreeNode* root){
    int n = 2; // 层数
    unsigned long long index = 1; // 编号
    unsigned long long sum = 1; // 上一层位置的个数h之合
    unsigned long long nCount = 1; // 当前这一层的节点个数（满二叉树的情况下应该有多少个）
 
    struct TreeNode *temp = root;
    while (temp->left == NULL && temp->right != NULL) {
        temp = temp->right;
    }
    memset(hashMap, 0, 3000*2*sizeof(int));
    hashMap[1][0] = 1;
    hashMap[1][1] = 1;
    DfxGetHashMap(temp->left, sum, nCount, n, index * 2);
    DfxGetHashMap(temp->right, sum, nCount, n, index * 2 + 1);
 
    int max = 0;
    for (int i = 1; hashMap[i][0] != 0; i++) {
        max = hashMap[i][1] > max ? hashMap[i][1] : max;
    }
    return max;
}