###### tags: `Leetcode` `medium` `tree` `bfs` `python` `c++`

# 662. Maximum Width of Binary Tree

## [題目連結:] https://leetcode.com/problems/maximum-width-of-binary-tree/

## 題目:
Given the root of a binary tree, return the **maximum width** of the given tree.

The **maximum width** of a tree is the maximum **width** among all levels.

The **width** of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is **guaranteed** that the answer will in the range of a **32-bit** signed integer.


## 解題想法:
* 此題為求二元樹的最大寬度

* 想法:
* 利用位置算寬度
* 設root位置為1
* 左子: 2 * n
* 右子: 2 * n +1
* 最後寬度為: 右子-左子+1
* example1:
* 最左子為5: 寬度4
* 最右子為9: 寬度7
* 所以res為7-4+1=4
* bfs每層更新max res

## Python:

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
    def insertLeft(self,node):
        if not self.left:
            self.left=TreeNode(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if not self.right:
            self.right=TreeNode(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def widthOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        #利用位置算寬度 root位置為1
        #左子:2*n 右子:2*n+1
        #最後寬度為: 右子-左子+1  example1: 左5(寬4) 右9(寬7)
        #bfs 更新每層的res
        cur_layer=[(root,1)]
        res=1
        while cur_layer:
            res=max(res,cur_layer[-1][1]-cur_layer[0][1]+1)
            next_layer=[]
            for node,pos in cur_layer:
                if node.left:
                    next_layer.append((node.left,pos*2))
                if node.right:
                    next_layer.append((node.right,pos*2+1))
            cur_layer=next_layer
        return res

root=TreeNode(1)
root.insertLeft(3)
root.insertRight(2)
root.left.insertLeft(5)
root.left.insertRight(3)
root.right.insertRight(9)
root.printTree()

result=Solution()
ans=result.widthOfBinaryTree(root)
print(ans)

## C++:
* 此題用c++解會一直溢位.......
* 看網上說: 對於極端的測試，每一層只有1個節點，而我們代碼中的坐標每次都要乘以2，所以在第32層之後就溢位了。
* 為了避免溢出的問題，如果這一層只有一個節點，則將這一層節點的坐標值重置為1，這樣就可以避免溢出。
* 結果還是溢位......
* 後來是將所有int改為終極大法: **unsigned long long**才成功submit

/**
 * 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)
            return 0;
        unsigned long long res=0;
        queue<pair<TreeNode*, unsigned long long>> que;
        que.push({root, 1});
        while (!que.empty()){
            int n=que.size();
            //An extreme test case: each layer has only 1 node
            //The coordinates in our code have to be multiplied by 2 every time
            //so it overflows after the 32nd layer.
            if (n==1)
                que.front().second=1;
            //In order to avoid the problem of overflow
            //If there is only one node in this layer
            //reset the coordinate value of the node in this layer to 1
            //so as to avoid overflow.
            unsigned long long left=que.front().second;
            unsigned long long right=left;
            for (int i=0; i<n; i++){
                TreeNode* curNode=que.front().first;
                right=que.front().second; que.pop();
                if (curNode->left)
                    que.push({curNode->left, right*2});
                if (curNode->right)
                    que.push({curNode->right, right*2+1});
            }
            res=max(res, right-left+1);
        }
        return res;
    }
};