南浔哪有做网站的,企业宣传册一般分几个模块,电子商务网站开发的说法,软件开发属于什么专业1. 题目
给定一个二叉树#xff0c;编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树#xff08;full binary tree#xff09;结构相同#xff0c;但一些节点为空。
每一层的宽度被定义为两个端点#xff08;该层最左和最右的非…1. 题目
给定一个二叉树编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树full binary tree结构相同但一些节点为空。
每一层的宽度被定义为两个端点该层最左和最右的非空节点两端点间的null节点也计入长度之间的长度。
示例 1:
输入: 1/ \3 2/ \ \ 5 3 9
输出: 4
解释: 最大值出现在树的第 3 层宽度为 4 (5,3,null,9)。示例 2:
输入: 1/ 3 / \ 5 3
输出: 2
解释: 最大值出现在树的第 3 层宽度为 2 (5,3)。示例 3:
输入: 1/ \3 2 / 5
输出: 2
解释: 最大值出现在树的第 2 层宽度为 2 (3,2)。示例 4:
输入: 1/ \3 2/ \ 5 9 / \6 7
输出: 8
解释: 最大值出现在树的第 4 层
宽度为 8 (6,null,null,null,null,null,null,7)。
注意: 答案在32位有符号整数的表示范围内。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximum-width-of-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
记录深度和每一层的最左侧节点位置中序遍历每层第一次碰到的节点位置用树的数组实现方式注意溢出每层pos*2很快就溢出了用ulong能过
class Solution {int ans;
public:int widthOfBinaryTree(TreeNode* root) {if(!root) return 0;vectorunsigned long LeftPosOflv;ans 1;dfs(root, 0, 0, LeftPosOflv);return ans;}void dfs(TreeNode* root, int depth, unsigned long pos, vectorunsigned long LeftPosOflv){if(!root) return;if(LeftPosOflv.size() depth)//第一次遇到的是该层最左边的LeftPosOflv.push_back(pos);ans max(ans, int(pos-LeftPosOflv[depth]1));dfs(root-left, depth1, 2*pos1, LeftPosOflv);dfs(root-right, depth1, 2*pos2, LeftPosOflv);}
};12 ms 16.3 MB
