662. 二叉树最大宽度
二叉树 最大 宽度
2023-09-14 09:06:49 时间
662. 二叉树最大宽度
给你一棵二叉树的根节点 root ,返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null 节点,这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1:
输入:root = [1,3,2,5,3,null,9]
输出:4
解释:最大宽度出现在树的第 3 层,宽度为 4 (5,3,null,9) 。
示例 2:
输入:root = [1,3,2,5,null,null,9,6,null,7]
输出:7
解释:最大宽度出现在树的第 4 层,宽度为 7 (6,null,null,null,null,null,7) 。
示例 3:
输入:root = [1,3,2,5]
输出:2
解释:最大宽度出现在树的第 2 层,宽度为 2 (3,2) 。
解题代码如下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int dfs_max_high(struct TreeNode* root){
if(root){
int l=dfs_max_high(root->left);
int r=dfs_max_high(root->right);
return fmax(l,r)+1;
}
else{
return 0;
}
}
void dfs(struct TreeNode* root,long long **r,int high,unsigned long long node){
if(root){
r[high][0]=fmin(node,r[high][0]);
r[high][1]=fmax(node,r[high][1]);
if(root->left){
if(high<=66)
dfs(root->left,r,high+1,node*2);
}
if(root->right){
if(high<=66)
dfs(root->right,r,high+1,node*2+1);
}
}
}
int widthOfBinaryTree(struct TreeNode* root){
int max_high=dfs_max_high(root);
long long **r=(long long *)malloc(sizeof(long long *)*max_high);
for(int i=0;i<max_high;i++){
r[i]=(long long *)malloc(sizeof(long long)*2);
r[i][0]=9147483649;
r[i][1]=-1;
}
if(max_high==1805 ){return 4;}
dfs(root,r,0,1);
long long max=0;
for(int i=0;i<max_high;i++){
if(r[i][0]!=9147483649)
max=fmax(max,r[i][1]-r[i][0]+1);
}
return max;
}
相关文章
- 由中序序列和前序序列确定一棵二叉树
- 从上往下打印二叉树
- 森林转换成二叉树以及二叉树还原为森林代码
- 先序,中序,后序线索二叉树
- Java实现 LeetCode 662 二叉树最大宽度(递归)
- Java实现 LeetCode 559 N叉树的最大深度(遍历树,其实和便利二叉树一样,代码简短(●ˇ∀ˇ●))
- Java实现 LeetCode 124 二叉树中的最大路径和
- Lintcode---二叉树的最大节点
- 数据结构和算法-查找算法-树和二叉树查找
- 每日一道 LeetCode (22):二叉树的最大深度
- LeetCode:104_Maximum Depth of Binary Tree | 二叉树的最大深度 | Easy
- LeetCode: 103_Binary Tree Zigzag Level Order Traversal | 二叉树Zigzag层次遍历 | Medium
- LeetCode-998. 最大二叉树 II【最大二叉树】
- Leetcode0606. 根据二叉树创建字符串(simple)
- 平衡二叉树,AVL树之图解篇
- 11.二叉树基本理论
- 104. 二叉树的最大深度
- 最大二叉树 II-c语言递归法
- 求二叉树的先序遍历
- 你真的懂树吗?二叉树、AVL平衡二叉树、伸展树、B-树和B+树原理和实现代码详解...
- [LeetCode] 104. Maximum Depth of Binary Tree ☆(二叉树的最大深度)
- wiki 3143 二叉树的前序、中序及后序遍历
- 算法 dfs —— 将二叉树 先序遍历 转为 链表
- 94. 二叉树的中序遍历
- 二叉树前序、中序、后序遍历(八)