【leetcode】【2022/8/27】662. 二叉树最大宽度

问题描述：

• 给定一棵二叉树的根节点 root，返回树的最大宽度。
  • 树的最大宽度是所有层中最大的宽度。
  • 每一层的宽度被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。
  • 将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
• 题目数据保证答案将会在 32 位带符号整数范围内。

核心思路：

• 该题用层次遍历解法比较直观。
  • 层次遍历通常用队列来实现，在每一层的遍历中可以判断当前层的最左和最右的非空节点。【为了方便取头节点和尾节点，所以用双端队列 deque，更直接的方法是用变长数组 vector 来模拟队列（数组的开销应该比双端队列要小），遍历完一整层就将数组置空】
  • 但宽度又包括非空节点之间的空节点个数，所以不能通过单纯计算当前层的节点个数直接返回。
  • 正确的方法应该是获得节点在满二叉树中对应的索引值，然后计算最左最右节点的索引差值。【当前节点为 i，其左子为 2*i，其右子为 2*i+1】
• 该题还有一个关键的地方就是数据量太大，索引的保存需要用 unsigned long long。

代码实现：

class Solution
{
public:
    int widthOfBinaryTree(TreeNode* root)
    {
        using ull = unsigned long long;
        using ptl = pair<TreeNode*, ull>;
        deque<ptl> dq;
        dq.push_back({root, 1L});
        ull ans = 1;
        while(!dq.empty())
        {
            ull fidx = dq.front().second; // front_idx，dq 中头部节点的索引
            ull bidx = dq.back().second; // back_idx，dq 中尾部节点的索引
            ans = max(ans, bidx - fidx + 1);
            int sz = dq.size();
            while(sz-- > 0)
            {
                TreeNode* tmp = dq.front().first;
                ull idx = dq.front().second;
                dq.pop_front();
                if(tmp->left) dq.push_back({tmp->left, idx*2});
                if(tmp->right) dq.push_back({tmp->right, idx*2+1});
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28