# 662. Maximum Width of Binary Tree

## problem description

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

**Example 1:**

```
Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).
```

**Example 2:**

```
Input: 

          1
         /  
        3    
       / \       
      5   3     

Output: 2
Explanation: The maximum width existing in the third level with the length 2 (5,3).
```

**Example 3:**

```
Input: 

          1
         / \
        3   2 
       /        
      5      

Output: 2
Explanation: The maximum width existing in the second level with the length 2 (3,2).
```

**Example 4:**

```
Input: 

          1
         / \
        3   2
       /     \  
      5       9 
     /         \
    6           7
Output: 8
Explanation:The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).


Note: Answer will in the range of 32-bit signed integer.
```

## algorithm thought

这题是求每一层的宽度。如果要求宽度，关键是要得到最左和最右节点的位置，然后将两个位置相减就行。关键是如何安排每个节点的值。这里可以用类似heap的表示法。

如果first index base 1，它的子树就是 2*index , 2*index+1. 如果first index base 0，它的子树就是 2*index+1 , 2*index+2

然后用DFS或者是BFS遍历数，将最右的值减去最左的值即可。但是如果就这样，不加处理，会在最后两个case失败。因为我们用int类型表达index，这样树最多只能有32层。如果用long类型，树也只能有64层，这两种类型都不能通过测试。

于是我参考了下discuss，发现有人在进入下一层的时候，将index module INT\_MAX。保证不溢出。修改代码之后发现能通过。

## code

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if(root==NULL)
            return 0;
        vector<long> left;
        return help(root,left,1,0);
    }
    long help(TreeNode*root,vector<long>&left,long pos,int level){
        if(root==NULL)
            return 0;
        if(level>=left.size())
            left.push_back(pos);
        //cout<<pos<<'-'<<left[level]<<' ';
        long le=help(root->left,left,(2*pos)%INT_MAX,level+1);
        return max(pos-left[level]+1,max(le,help(root->right,left,(2*pos+1)%INT_MAX,level+1)));
    }
};
```

## algorithm analysis

DFS遍历树，每次遍历中间时间复杂度为O(1)，最后时间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/662.-maximum-width-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.