题目描述

给你一棵二叉树的根节点 root ，返回树的 最大宽度 。

树的 最大宽度 是所有层中最大的 宽度 。

每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。

题目数据保证答案将会在 32 位 带符号整数范围内。

样例

blablabla

算法1

(层序遍历+二叉树性质)

blablabla

时间复杂度

参考文献

java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int l=0,r=-1;
        TreeNode q[] = new TreeNode [3001];
        int iq[]= new int [3001];

        if(root==null) return 0;
        q[++r]=root;
        iq[r]=1;
     int ans=0;
        while(l<=r){
            int sz=r-l+1;
        ans=Math.max(ans,iq[r]-iq[l]+1);
        for(int i=0;i<sz;i++){


            TreeNode cur = q[l];
            if(cur.left!=null){
                q[++r]=cur.left;
                iq[r]=2*iq[l];
            }
             if(cur.right!=null){
                q[++r]=cur.right;
                iq[r]=2*iq[l]+1;
            }
            l++;

              }
        }
        return ans;
    }
}
blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla