今天面試中面試官的第一個題就是讓我寫一個二叉樹的實現(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)（下面會按照這個順序展示代碼）

1. ViewController.m
2. Model.h
3. 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é)束