Medium

题目描述

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。

每一层的宽度被定义为两个端点（该层上的最左和最右的非空节点，两端点间的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

解题思路

解题思路

这道题的关键在于理解"宽度"的定义：每一层的宽度是最左端非空节点到最右端非空节点之间的距离，包括中间的空节点。

核心思想

我们可以给每个节点分配一个索引位置，就像完全二叉树一样：

  • 根节点索引为0（或1）
  • 对于索引为i的节点，其左孩子索引为2i，右孩子索引为2i+1

算法步骤

  1. 使用BFS遍历树，记录每个节点及其索引
  2. 对于每一层，记录最左边和最右边节点的索引
  3. 该层宽度 = 最右索引 - 最左索引 + 1
  4. 维护最大宽度

注意事项

为了防止索引溢出，我们可以在每一层开始时将所有索引减去该层最左节点的索引，进行标准化处理。

这样既保持了相对位置关系，又避免了数值过大的问题。使用BFS可以很方便地按层处理，时间复杂度为O(n)，空间复杂度为O(w)，其中w是树的最大宽度。

代码实现

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        
        queue<pair<TreeNode*, unsigned long long>> q;
        q.push({root, 0});
        int maxWidth = 1;
        
        while (!q.empty()) {
            int size = q.size();
            unsigned long long left = q.front().second;
            unsigned long long right = left;
            
            for (int i = 0; i < size; i++) {
                auto [node, idx] = q.front();
                q.pop();
                right = idx;
                
                if (node->left) {
                    q.push({node->left, 2 * (idx - left)});
                }
                if (node->right) {
                    q.push({node->right, 2 * (idx - left) + 1});
                }
            }
            
            maxWidth = max(maxWidth, (int)(right - left + 1));
        }
        
        return maxWidth;
    }
};

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([(root, 0)])
        max_width = 1
        
        while queue:
            size = len(queue)
            left = queue[0][1]
            right = left
            
            for _ in range(size):
                node, idx = queue.popleft()
                right = idx
                
                if node.left:
                    queue.append((node.left, 2 * (idx - left)))
                if node.right:
                    queue.append((node.right, 2 * (idx - left) + 1))
            
            max_width = max(max_width, right - left + 1)
        
        return max_width

public class Solution {
    public int WidthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        
        var queue = new Queue<(TreeNode node, ulong idx)>();
        queue.Enqueue((root, 0));
        int maxWidth = 1;
        
        while (queue.Count > 0) {
            int size = queue.Count;
            ulong left = queue.Peek().idx;
            ulong right = left;
            
            for (int i = 0; i < size; i++) {
                var (node, idx) = queue.Dequeue();
                right = idx;
                
                if (node.left != null) {
                    queue.Enqueue((node.left, 2 * (idx - left)));
                }
                if (node.right != null) {
                    queue.Enqueue((node.right, 2 * (idx - left) + 1));
                }
            }
            
            maxWidth = Math.Max(maxWidth, (int)(right - left + 1));
        }
        
        return maxWidth;
    }
}

var widthOfBinaryTree = function(root) {
    if (!root) return 0;
    
    const queue = [[root, 0n]];
    let maxWidth = 1;
    
    while (queue.length > 0) {
        const size = queue.length;
        const left = queue[0][1];
        let right = left;
        
        for (let i = 0; i < size; i++) {
            const [node, idx] = queue.shift();
            right = idx;
            
            if (node.left) {
                queue.push([node.left, 2n * (idx - left)]);
            }
            if (node.right) {
                queue.push([node.right, 2n * (idx - left) + 1n]);
            }
        }
        
        maxWidth = Math.max(maxWidth, Number(right - left + 1n));
    }
    
    return maxWidth;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(w)

其中 n 是树中节点的数量，w 是树的最大宽度（最坏情况下为 O(n)）。