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;
vector<unsigned long> LeftPosOflv;
ans = 1;
dfs(root, 0, 0, LeftPosOflv);
return ans;
}
void dfs(TreeNode* root, int depth, unsigned long pos, vector<unsigned long> &LeftPosOflv)
{
if(!root) return;
if(LeftPosOflv.size() <= depth)//第一次遇到的是该层最左边的
LeftPosOflv.push_back(pos);
ans = max(ans, int(pos-LeftPosOflv[depth]+1));
dfs(root->left, depth+1, 2*pos+1, LeftPosOflv);
dfs(root->right, depth+1, 2*pos+2, LeftPosOflv);
}
};
12 ms 16.3 MB