LeetCode 662. 二叉树最大宽度

题目描述

662. 二叉树最大宽度

解法

这道题画个图就清楚很多了，先理解一下为什么我们要编号

如果这道题让你用层遍历会怎么做，即使是空指针的结点也应该记为 -1 这样的一个元素压入到队列中，然后统计每层的宽度

序号的作用就是这样，代替了我们去一个个将空指针转换成 -1 放入到队列中

那么有了序号还需要层遍历吗？不需要，因为在先序遍历中，我们永远都是先访问到这一层最左边的结点，所以先序遍历就可以帮助我们记录到每一层序号最小的元素

需要注意的是在 C++ 代码中，需要使用 usigned long long 来存储 index

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
using ULL = unsigned long long;

class Solution {
private:
    unordered_map<int, ULL> hash;
    int res = -1;
public:
    int widthOfBinaryTree(TreeNode* root) {
        return dfs(root, 0, 1LL); 
    }
    ULL dfs(TreeNode* root, int depth, ULL index){
        if (root == nullptr) return 0LL;
        if (hash.count(depth) == 0) hash[depth] = index;
        return max({index - hash[depth] + 1LL, dfs(root->left, depth + 1, index * 2), dfs(root->right, depth + 1, index * 2 + 1)});

    }
};