今天面试中面试官的第一个题就是让我写一个二叉树的实现，时间是两个小时，我开始用递归算法写了一个，面试官说网上也有很多递归算法（言外之意就是有抄袭的嫌疑），让我不用递归，重新写一份，今天我就把我自己没有使用递归的写法分享一下，网上较多的递归算法就不展示了
问题
输入 数组['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o'],构建上面的二叉树。
1.不能抄袭网上答案。数组是二叉树的层序遍历次序。
2.我只解答题目疑问，不解答做题过程。
3.这个题目二叉树只有4层，代码可以只实现这4层的构造。但是算法要想到很多层的情况。
3.这是初试。通过会有电话面试。
4.要求用xcode oc 做。
5.做题时间2个 小时内。
以上是面试官的原问题
我的答案展示
目录结构（下面会按照这个顺序展示代码）
- ViewController.m
- Model.h
- Model.m
- ViewController.m
#import "ViewController.h"
#import "Model.h"
@interface ViewController ()
@end
@implementation ViewController
- (void)viewDidLoad {
[super viewDidLoad];
Model *model = [self makeWithListArray:@[@"a",@"b",@"c",@"d",@"e",@"f",@"g",@"h",@"i",@"j",@"k",@"l",@"m",@"n",@"o"]];
}
/// 根据数据构建二叉树模型
/// @param array 元素数组
- (nullable Model *)makeWithListArray:(NSArray<NSString *> *)array{
if (array.count == 0) return nil;//数组判空（返回模型可以为空）
Model *model = [[Model alloc] init];
model.subObjectCount = 0;
for (NSInteger i = 0 ; i < array.count; i++) {
model.value = array[i];//设置节点（赋值的set方法里面做了无限往下延续操作）
}
return model;
}
@end
- Model.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface Model : NSObject
@property (nonatomic , strong) NSString *value;//节点值
@property (nonatomic , assign) NSInteger subObjectCount;//节点以下数据量
@property (nonatomic , strong) Model *left;
@property (nonatomic , strong) Model *right;
@end
NS_ASSUME_NONNULL_END
- Model.m（重点）
#import "Model.h"
@interface Model()
@property (nonatomic , assign) NSInteger subLevelNum;//层级
@property (nonatomic , assign) NSInteger subMaxNum;//当前层级最大容纳数量
@end
@implementation Model
- (instancetype)init
{
if (self = [super init]) {
self.subMaxNum = 1;
self.subLevelNum = 0;
}
return self;
}
//当前值
- (void)setValue:(NSString *)value
{
self.subObjectCount += 1;
if (_value.length == 0) {
_value = value;
}else{
if (self.subObjectCount > self.subMaxNum) {
self.subLevelNum += 1;
if (self.subLevelNum == 1) {
self.subMaxNum = 3;
}else{
NSInteger num = 2;
for (NSInteger i = 1; i < self.subLevelNum; i++) {
num *= 2;
}
self.subMaxNum += num;
}
}
NSInteger newSubCount = (self.subMaxNum-1)*0.5;
if (self.left.subObjectCount < newSubCount) {
self.left.value = value;
}else{
self.right.value = value;
}
}
}
//左侧model
- (Model *)left
{
if (!_left) {
_left = [[Model alloc] init];
_left.subObjectCount = 0;
}
return _left;
}
//右侧model
- (Model *)right
{
if (!_right) {
_right = [[Model alloc] init];
_right.subObjectCount = 0;
}
return _right;
}
@end
重点就是Model.m里面的当前值赋值的set方法，小伙伴们看着如果有点懵的话，可以把三部分代码复制到xcode里面运行一下就了解了
结束
