leetcode：662. 二叉树最大宽度

题目

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

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

示例：

  1. 输入: 
  3.            1
  4.          /   \
  5.         3     2
  6.        / \     \  
  7.       5   3     9 
  9. 输出: 4
  10. 解释: 最大值出现在树的第 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)。

解答 & 代码

层序遍历：用队列记录 pair<节点，节点编号>，根节点的编号为 1，左孩子节点编号 = 根结点编号 2，右孩子节点编号 = 根节点编号 2 + 1
对于每一层，层宽度 = 最右边的节点编号 - 最左边的节点编号

/**
 * 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) {
        if(root == nullptr)
            return 0;

        int maxWidth = 1;
        // 注意节点编号要用 unsigned long long！
        queue<pair<TreeNode*, unsigned long long>> nodePosQ;
        nodePosQ.push(make_pair(root, 1));
        while(!nodePosQ.empty())
        {
            // 当前层宽度 = 最右边的节点编号 - 最左边的节点编号
            maxWidth = max(maxWidth, 
                        int(nodePosQ.back().second - nodePosQ.front().second + 1));
            int levelSize = nodePosQ.size();
            for(int i = 0; i < levelSize; ++i)
            {
                TreeNode* cur = nodePosQ.front().first;
                unsigned long long pos = nodePosQ.front().second;
                nodePosQ.pop();

                if(cur->left != nullptr)
                    nodePosQ.push(make_pair(cur->left, pos * 2));
                if(cur->right != nullptr)
                    nodePosQ.push(make_pair(cur->right, pos * 2 + 1));
            }
        }
        return maxWidth;
    }
};

复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：遍历每个节点一次
  • 空间复杂度 O(N)：队列的大小

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 72.26% 的用户
内存消耗：16.9 MB, 在所有 C++ 提交中击败了 43.89% 的用户