662.二叉树最大宽度

【LetMeFly】662.二叉树最大宽度：一组奇怪的数据

力扣题目链接：https://leetcode.cn/problems/maximum-width-of-binary-tree/

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

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

示例 1:

输入: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

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

示例 2:

输入: 

          1
         /  
        3    
       / \       
      5   3     

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

示例 3:

输入: 

          1
         / \
        3   2 
       /        
      5      

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

示例 4:

输入: 

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

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

方法一：层次遍历

层序遍历二叉树，在遍历的同时，二叉树的“坐标”同时入队。

在处理每一层时，更新最左和最右的坐标。

处理完这一层后，$最右 - 最左 + 1$就是这层的宽度。

处理一个节点时，若此节点具有左子节点，那么左子节点的编号为这个节点编号的二倍

若具有右子节点，那么右子节点的编号是这个节点编号的二倍+1

具体原因为：

• 时间复杂度$O(n)$，其中$n$为二叉树节点个数
• 空间复杂度$O(n)$

提交我下面的代码并不能通过这道题，因为这道题数据有一组似乎得手写高精度。官方题解也溢出了（截止至20220827 15:03）。

已反馈至Github:https://github.com/LeetCode-Feedback/LeetCode-Feedback/issues/8816

至发文为止不能AC的代码

C++

typedef unsigned long long ull;
// typedef __int128 ull;
typedef pair<TreeNode*, ull> pii;
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        ull ans = 0;
        queue<pii> q;
        q.push({root, 1});
        ull lastL, lastR;
        // int cntDebug = 0;
        while (q.size()) {
            
            // cntDebug++;
            // if (cntDebug > 1750) {
            //     printf("q.size() = %lld, q:[");
            //     // queue<pii> q2, q3 = q;
            //     // while (q3.size()) {
            //     //     q2.push(q3.front());
            //     //     q3.pop();
            //     // }
            //     // while (q2.size()) {
            //     //     cout << q2.front().first->val << ", ";
            //     // }
            // }
            ull mostL = q.front().second, mostR = mostL;
            for (int i = q.size(); i > 0; i--) {
                auto[node, loc] = q.front();
                // printf("loc = %llu\n", loc);
                // if (node->val) {
                //     printf("node->val = %d, loc = %llu\n", node->val, loc);
                // }
                q.pop();
                mostL = min(mostL, loc);
                mostR = max(mostR, loc);
                if (node->left) {
                    q.push({node->left, loc * 2 - 1});
                }
                if (node->right) {
                    q.push({node->right, loc * 2});
                }
            }
            lastL = mostL, lastR = mostR;
            ans = max(ans, mostR - mostL + 1);
            // if (cntDebug > 1750) {
            //     // cout << "mostL = " << lastL << ", mostR = " << lastR << endl;
            //     printf("mostL = %llu, mostR = %llu\n", mostL, mostR, q.size());
            // }
        }
        return ans;
    }
};

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-03 18:17:09
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-03 21:01:10
 */
typedef unsigned long long ull;

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        ull ans = 1;
        queue<pair<TreeNode*, ull>> q;
        q.push({root, 0});
        while (q.size()) {
            cout << q.size() << endl;
            ull m = -1, M = 0;  // 0是最小值，-1是最大值（2^{64}-1）
            for (int i = q.size(); i > 0; i--) {
                auto [node, num] = q.front();
                cout << node->val << ',' << num << endl;
                q.pop();
                m = min(m, num);
                M = max(M, num);
                if (node->left) {
                    q.push({node->left, num * 2 + 1});
                }
                if (node->right) {
                    q.push({node->right, num * 2 + 2});
                }
            }
            // printf("ans = max(%lld, %lld) = %lld\n", ans, M - m + 1, max(ans, M - m + 1));
            ans = max(ans, M - m + 1);
        }
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-05 22:11:08
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-05 22:14:01
'''
from typing import Optional

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 1
        q = [(root, 0)]
        while q:
            nextQ = []
            ans = max(ans, q[-1][1] - q[0][1] + 1)
            for node, num in q:
                if node.left:
                    nextQ.append((node.left, num * 2 + 1))
                if node.right:
                    nextQ.append((node.right, num * 2 + 2))
            q = nextQ
        return ans

Golang

/*
 * @Author: LetMeFly
 * @Date: 2025-03-05 22:36:39
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-05 22:42:05
 */
package main

// type TreeNode struct {
//     Val int
//     Left *TreeNode
//     Right *TreeNode
// }

type pair_MWOBT struct {
    node *TreeNode
    num int
}

func widthOfBinaryTree(root *TreeNode) (ans int) {
    q := []pair_MWOBT{{root, 0}}
    for len(q) > 0 {
        nextQ := []pair_MWOBT{}
        ans = max(ans, q[len(q) - 1].num - q[0].num + 1)
        for _, pair := range q {
            if pair.node.Left != nil {
                nextQ = append(nextQ, pair_MWOBT{pair.node.Left, pair.num * 2 + 1})
            }
            if pair.node.Right != nil {
                nextQ = append(nextQ, pair_MWOBT{pair.node.Right, pair.num * 2 + 2})
            }
        }
        q = nextQ
    }
    return ans
}

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/126558271