世间无限丹青手
一片伤心画不成
题目还是蛮简单的，以前这个层序遍历我都是用递归。。。
其实dfs代码很短，也更好理解，但我怕自己忘了bfs了，就写一次2333。
一般来说，这种要求统计某一层信息的，需要利用额外的东西记录层数信息，所以这种情况下递归就很合适，进入下一层递归就意味着到了树的下一层结点。
同时也需要掌握父子结点之间的一些联系，比如在完全二叉树中，按照从上到下，从左到右的顺序，父结点和子结点的索引应该满足 left_child = father * 2, right_child = father * 2 + 1。直到这个关系，无论是bfs还是dfs，都会简单啦。。。
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
using ll = long long;
if (root == nullptr) return 0;
queue<pair<TreeNode *, int>> q;
q.push({root, 1});
ll ans = 1, left = 1;
while (!q.empty()) {
auto pair_node = q.front();
q.pop();
TreeNode *node = pair_node.first;
ll index = pair_node.second;
if (index >= 2 * left)
left = index;
if (node->left)
q.push({node->left, index * 2});
if (node->right)
q.push({node->right, index * 2 + 1});
ans = max(ans, index - left + 1);
}
return ans;
}
};
