BFS and binary tree
662. Maximum Width of Binary Tree
A simple way is recursion and record the maximum index and minimum index for each level. The final result will be the largest difference. The time complexity is O(n) as the recursion process and the space complexity is also O(n). The recursion will use memory.
One thing we should pay attention is when the bianry tree is very unbalanced, then the tree will be changed to very close to a linked list. If we have n layers, the index will be a very large number. We may have overflow. If we set the index as unsigned long long. It can get AC.
/**
* 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 {
unordered_map<int, unsigned long long> small, large;
public:
void helper(TreeNode* node, int level,unsigned long long i){
if (!node)return;
if (small.count(level))
{
small[level] = min(small[level], i);
large[level] = max(large[level], i);
}
else
{
small[level] = i;
large[level] = i;
}
helper(node->left, level+1, 2*i);
helper(node->right, level+1, 2*i+1);
}
int widthOfBinaryTree(TreeNode* root) {
unsigned long long ret = 0;
helper(root, 0, 1);
for(auto x:small)
{
ret = max(ret, large[x.first] - small[x.first]);
}
return int(ret+1);
}
};We have another way to get rid of overflow. If the current level has only one element, we can set the index of this current level to 1 as it will not have a influence for the future caculation.
The reason that I start the index from 1 instead of 0 is if we start from 1, we will have left node index as 2 and right as 3.
2/2 and 3/2 can get the partent node’s index easiler.
We can not directly modify this solution as we are using recursion to solve this problem. Recursion is using a DFS approach.
/**
* 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 {
unordered_map<int, int> small, large;
public:
int widthOfBinaryTree(TreeNode* root)
{
int ret = 1;
deque<TreeNode*> dq;
if(root)dq.push_back(root);
root->val = 1;
while(!dq.empty())
{
ret = max(ret, dq.back()->val - dq.front()->val + 1);
int L = dq.size();
if (L==1)
{
dq.front()->val = 1;
}
while(L--)
{
TreeNode* node = dq.front();
dq.pop_front();
if(node->left)
{
node->left->val = node->val*2;
dq.push_back(node->left);
}
if(node->right)
{
node->right->val = node->val*2 + 1;
dq.push_back(node->right);
}
}
}
return ret;
}
};103. Binary Tree Zigzag Level Order Traversal
/**
* 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:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ret;
if (!root) return ret;
queue<TreeNode*> q;
q.push(root);
int level = 0 ;
while (!q.empty())
{
int len = q.size();
vector<int> this_ret;
while(len--)
{
auto node = q.front();q.pop();
this_ret.push_back(node->val);
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
if (level%2==1) reverse(this_ret.begin(), this_ret.end());
ret.push_back(this_ret);
level++;
}
return ret;
}
};
