题目描述

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

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

样例

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

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

输入: 

          1
         /  
        3    
       / \       
      5   3     

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

输入: 

          1
         / \
        3   2 
       /        
      5      

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

输入: 

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

说明

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

算法1 新数据无法通过

(深度优先遍历) $O(n)$

1. 对整个树进行深度优先遍历。遍历时，记录每一层最左边结点的编号和最右边结点的编号。
2. 编号规则如下，根结点编号为 0。某个结点的左儿子结点编号为当前结点的编号乘 2；右儿子结点的编号为当前结点的编号乘 2 再加 1。
3. 用两个数组记录每一层最左边结点的编号和最右边结点的编号，由于遍历时，总是从左儿子开始，故最左边结点的编号只需要记录一次，而最右边结点需要每次更新。
4. 由于题目数据原因，该方法仅在编号不超过 64 位整数的情况下适用。由于新数据中结点的层数可能很深（但答案很小，所以无法通过）。

时间复杂度

• 每个结点遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储系统栈和数组。

C++ 代码 整数溢出

/**
 * 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) {}
 * };
 */
class Solution {
public:
    #define LL long long
    void dfs(TreeNode *r, int depth, LL cur_pos, vector<LL> &left, vector<LL> &right) {
        if (r == NULL)
            return;
        if (left.size() == depth)
            left.push_back(cur_pos);

        if (right.size() == depth)
            right.push_back(cur_pos);

        right[depth] = cur_pos;
        dfs(r->left, depth + 1, cur_pos << 1, left, right);
        dfs(r->right, depth + 1, cur_pos << 1 | 1, left, right);
    }

    int widthOfBinaryTree(TreeNode* root) {
        vector<LL> left, right;
        dfs(root, 0, 0, left, right);
        int n = min(left.size(), right.size());
        LL ans = 0;

        for (int i = 0; i < n; i++)
            ans = max(ans, right[i] - left[i] + 1);

        return ans;
    }
};

算法2

(层级遍历) $O(n)$

1. 对整个树进行层级遍历。遍历时，记录每一层所有结点的编号。
2. 编号规则如下，根结点编号为 0。某个结点的左儿子结点编号为当前结点的编号乘 2；右儿子结点的编号为当前结点的编号乘 2 再加 1。
3. 遍历完一层后，我们进行编号收缩，以最小编号作为偏移量，让当前层所有编号都减去这个偏移量，然后再进行遍历编号。
4. 通过编号收缩，保证编号的范围不会超过答案，所以不会

时间复杂度

• 每个结点遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储和数组。

C++ 代码

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        #define LL long long
        if (!root) return 0;

        vector<pair<TreeNode*, LL>> pr;
        pr.emplace_back(root, 0);

        LL ans = 0;
        while (!pr.empty()) {
            LL offset = pr.front().second;
            for (int i = 0; i < pr.size(); i++)
                pr[i].second -= offset;

            ans = max(ans, pr.back().second + 1);

            vector<pair<TreeNode*, LL>> nt;
            for (int i = 0; i < pr.size(); i++) {
                TreeNode *u = pr[i].first;
                LL pos = pr[i].second;

                if (u->left) nt.emplace_back(u->left, pos << 1);
                if (u->right) nt.emplace_back(u->right, pos << 1 | 1);
            }

            pr = nt;
        }

        return ans;
    }
};