今天面試中面試官的第一個題就是讓我寫一個二叉樹的實現(xiàn)，時間是兩個小時徘跪，我開始用遞歸算法寫了一個，面試官說網(wǎng)上也有很多遞歸算法（言外之意就是有抄襲的嫌疑）顶籽，讓我不用遞歸，重新寫一份银觅，今天我就把我自己沒有使用遞歸的寫法分享一下礼饱，網(wǎng)上較多的遞歸算法就不展示了
問題
輸入 數(shù)組['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o'],構(gòu)建上面的二叉樹。
1.不能抄襲網(wǎng)上答案究驴。數(shù)組是二叉樹的層序遍歷次序镊绪。
2.我只解答題目疑問，不解答做題過程洒忧。
3.這個題目二叉樹只有4層蝴韭，代碼可以只實現(xiàn)這4層的構(gòu)造。但是算法要想到很多層的情況跑慕。
3.這是初試万皿。通過會有電話面試摧找。
4.要求用xcode oc 做核行。
5.做題時間2個 小時內(nèi)牢硅。
以上是面試官的原問題
我的答案展示
目錄結(jié)構(gòu)（下面會按照這個順序展示代碼）
- 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"]];
}
/// 根據(jù)數(shù)據(jù)構(gòu)建二叉樹模型
/// @param array 元素數(shù)組
- (nullable Model *)makeWithListArray:(NSArray<NSString *> *)array{
if (array.count == 0) return nil;//數(shù)組判空（返回模型可以為空）
Model *model = [[Model alloc] init];
model.subObjectCount = 0;
for (NSInteger i = 0 ; i < array.count; i++) {
model.value = array[i];//設(shè)置節(jié)點（賦值的set方法里面做了無限往下延續(xù)操作）
}
return model;
}
@end
- Model.h
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface Model : NSObject
@property (nonatomic , strong) NSString *value;//節(jié)點值
@property (nonatomic , assign) NSInteger subObjectCount;//節(jié)點以下數(shù)據(jù)量
@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;//當(dāng)前層級最大容納數(shù)量
@end
@implementation Model
- (instancetype)init
{
if (self = [super init]) {
self.subMaxNum = 1;
self.subLevelNum = 0;
}
return self;
}
//當(dāng)前值
- (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;
}
}
}
//左側(cè)model
- (Model *)left
{
if (!_left) {
_left = [[Model alloc] init];
_left.subObjectCount = 0;
}
return _left;
}
//右側(cè)model
- (Model *)right
{
if (!_right) {
_right = [[Model alloc] init];
_right.subObjectCount = 0;
}
return _right;
}
@end
重點就是Model.m里面的當(dāng)前值賦值的set方法，小伙伴們看著如果有點懵的話芝雪，可以把三部分代碼復(fù)制到xcode里面運行一下就了解了
結(jié)束
