二叉树最大宽度
地址:https://leetcode-cn.com/problems/maximum-width-of-binary-tree/
给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（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位有符号整数的表示范围内。
使用OC 我们需要创建一个BinaryTreeNode节点model 里面的对象如下
/**
* 值
*/
@property (nonatomic, assign) NSInteger value;
/**
* 左节点
*/
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/**
* 右节点
*/
@property (nonatomic, strong) BinaryTreeNode *rightNode;
层次遍历
这里首先是层次遍历，将每层区分出来
每层记录每层最开始节点的下标 left
每层其他的节点都剪去最开始的 就为每个节点的宽度
选出最大的宽度 即为结果
- (NSInteger)widthOfBinaryTree:(BinaryTreeNode *)root
{
if (root == nil) {
return 0;
}
NSMutableArray *dataArray = [NSMutableArray array];
[dataArray addObject:root];
///用于判断某层
NSInteger count = dataArray.count;
NSInteger levelMax = dataArray.count;
BOOL isNewLevel = NO;
BOOL isNewNode = NO;
///每层最左侧的位置
NSInteger left = 0;
///最大宽度
NSInteger max = 0;
while (dataArray.count > 0) {
BinaryTreeNode *node = [dataArray firstObject];
[dataArray removeObjectAtIndex:0];
count--;
///这里将左右都放入队列中，不需要判断左右是否为空
if ([node isKindOfClass:[BinaryTreeNode class]] && node.leftNode) {
[dataArray addObject:node.leftNode];
isNewNode = YES;
} else {
[dataArray addObject:@"NULL"];
}
if ([node isKindOfClass:[BinaryTreeNode class]] && node.rightNode) {
[dataArray addObject:node.rightNode];
isNewNode = YES;
} else {
[dataArray addObject:@"NULL"];
}
/// 同一层 且左侧没有值 left赋值
if (isNewLevel == NO && left == 0 && [node isKindOfClass:[BinaryTreeNode class]]) {
left = levelMax - count;
}else {
isNewLevel = YES;
}
if ([node isKindOfClass:[BinaryTreeNode class]]) {
NSInteger nodeMax = levelMax - count - left + 1;
max = MAX(max, nodeMax);
}
if (count == 0) {
if (isNewNode == NO) {
[dataArray removeAllObjects];
}
count = dataArray.count;
levelMax = dataArray.count;
left = 0;
isNewLevel = NO;
isNewNode = NO;
}
}
return max;
}
验证
{
/*
1
/ \
3 2
/ \ \
5 3 9
*/
BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
node1.value = 1;
BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
node2.value = 3;
BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
node3.value = 2;
node1.leftNode = node2;
node1.rightNode = node3;
BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
node4.value = 5;
BinaryTreeNode *node5 = [[BinaryTreeNode alloc] init];
node5.value = 3;
node2.leftNode = node4;
node2.rightNode = node5;
BinaryTreeNode *node6 = [[BinaryTreeNode alloc] init];
node6.value = 9;
node3.rightNode = node6;
NSInteger aa = [self widthOfBinaryTree:node1];
NSLog(@"aa is %ld",aa);
}
{
/*
1
/
3
/ \
5 3
*/
BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
node1.value = 1;
BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
node2.value = 3;
node1.leftNode = node2;
BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
node3.value = 5;
BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
node4.value = 3;
node2.leftNode = node3;
node2.rightNode = node4;
NSInteger aa = [self widthOfBinaryTree:node1];
NSLog(@"aa is %ld",aa);
}
{
/*
1
/ \
3 2
/
5
*/
BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
node1.value = 1;
BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
node2.value = 3;
BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
node3.value = 2;
node1.leftNode = node2;
node1.rightNode = node3;
BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
node4.value = 5;
node2.leftNode = node4;
NSInteger aa = [self widthOfBinaryTree:node1];
NSLog(@"aa is %ld",aa);
}
{
/*
1
/ \
3 2
/ \
5 9
/ \
6 7
*/
BinaryTreeNode *node1 = [[BinaryTreeNode alloc] init];
node1.value = 1;
BinaryTreeNode *node2 = [[BinaryTreeNode alloc] init];
node2.value = 3;
BinaryTreeNode *node3 = [[BinaryTreeNode alloc] init];
node3.value = 2;
node1.leftNode = node2;
node1.rightNode = node3;
BinaryTreeNode *node4 = [[BinaryTreeNode alloc] init];
node4.value = 5;
node2.leftNode = node4;
BinaryTreeNode *node5 = [[BinaryTreeNode alloc] init];
node5.value = 9;
node3.rightNode = node5;
BinaryTreeNode *node6 = [[BinaryTreeNode alloc] init];
node6.value = 6;
node4.leftNode = node6;
BinaryTreeNode *node7 = [[BinaryTreeNode alloc] init];
node7.value = 7;
node5.rightNode = node7;
NSInteger aa = [self widthOfBinaryTree:node1];
NSLog(@"aa is %ld",aa);
}
网友评论