NC204. 二叉树的最大宽度
描述
示例1
输入:
{1,2,3,4,#,4,5}
输出:
4
说明:
如题面图示例2
输入:
{1}
输出:
1
示例3
输入:
{1,2,3,4,#,4,5,6,#,1}
输出:
5
说明:
最后一层的宽度为5Go 解法, 执行用时: 2ms, 内存消耗: 784KB, 提交时间: 2022-02-09
package main
import . "nc_tools"
/*
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
func widthOfBinaryTree( root *TreeNode ) int {
if root==nil{
return 0
}
q:=make([]*TreeNode,0)
q=append(q, root)
l:=0
ans:=1
for len(q)>0{
l=len(q)
for i:=0;i<l;i++{
if q[i]!=nil{
q = append(q,q[i].Left )
q = append(q,q[i].Right )
}else{
q = append(q,nil )
q = append(q,nil )
}
}
q=q[l:]
i,j:=0,len(q)-1
for i<len(q)&&j>=0&&(q[i]==nil||q[j]==nil){
if q[i]==nil{
i++
}
if q[j]==nil{
j--
}
}
if i>j{
break
}
q=q[i:j+1]
l=len(q)
ans=max(ans,l)
}
return ans
}
func max(a,b int)int{
if a>b{
return a
}
return b
}
C++ 解法, 执行用时: 3ms, 内存消耗: 300KB, 提交时间: 2021-12-19
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
struct Node {
int minv;
int maxv;
Node() {};
Node(int m1, int m2) : minv(m1), maxv(m2) {};
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
if(root == NULL) {
return 0;
}
helper(root, 0, 0);
int maxd = 0;
for(auto iter = mp.begin(); iter != mp.end(); iter++) {
maxd = max(maxd, iter->second.maxv - iter->second.minv + 1);
}
return maxd;
}
private:
void helper(TreeNode* nd, int depth, int seq) {
if(nd == NULL) {
return;
}
add(depth, seq);
helper(nd->left, depth+1, 2*seq);
helper(nd->right, depth+1, 2*seq+1);
}
private:
void add(int depth, int seq) {
auto iter = mp.find(depth);
if(iter == mp.end()) {
mp[depth] = Node(seq, seq);
} else {
if(iter->second.minv > seq) {
iter->second.minv = seq;
}
if(iter->second.maxv < seq) {
iter->second.maxv = seq;
}
}
}
private:
map<int, Node> mp;
};
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-05-16
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int ans = 1;
queue<pair<TreeNode*, int> > q;
q.push({root, 1});
while(q.size())
{
int length = q.size();
int l = INT32_MAX, r = 0;
while(length--)
{
auto temp = q.front();
q.pop();
l = min(temp.second, l);
r = max(r, temp.second);
if(temp.first->left) q.push({temp.first->left, temp.second * 2});
if(temp.first->right) q.push({temp.first->right, temp.second * 2 + 1});
}
ans = max(ans, r - l + 1);
}
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-04-20
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
if (!root) {
return 0;
}
queue<TreeNode*> q;
q.push(root);
int ans = INT_MIN;
while (!q.empty()) {
ans = max(ans, q.back()->val - q.front()->val + 1);
int sz = q.size();
int offset = q.front()->val;
while (sz-- > 0) {
root = q.front();
q.pop();
int val = root->val - offset;
if (root->left) {
root->left->val = 2 * val + 1;
q.push(root->left);
}
if (root->right) {
root->right->val = 2 * val + 2;
q.push(root->right);
}
}
}
return ans;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 388KB, 提交时间: 2022-03-29
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
int widthOfBinaryTree(TreeNode* root) {
// write code here
if(root == nullptr){
return 0;
}
if(!(root->left && root->right)){
return 1;
}
int Size = 0;
queue<pair<TreeNode*,int>> q;
q.push({root,1});
int res = INT_MIN;
while(!q.empty()){
Size = q.size();
int max1 = INT_MIN, min1 = INT_MAX;
for(int i = 0; i< Size ;i++){
auto node = q.front();
q.pop();
if(node.first->left){
q.push({node.first->left, node.second * 2});
max1 = max(max1, node.second * 2);
min1 = min(min1, node.second * 2);
}
if(node.first->right){
q.push({node.first->right, node.second * 2+1});
max1 = max(max1, node.second * 2 +1);
min1 = min(min1, node.second * 2 +1);
}
}
res = max(res, max1-min1 +1);
}
return res;
}
};