iOS开发之二叉树OC实现

今天面试中面试官的第一个题就是让我写一个二叉树的实现，时间是两个小时，我开始用递归算法写了一个，面试官说网上也有很多递归算法（言外之意就是有抄袭的嫌疑），让我不用递归，重新写一份，今天我就把我自己没有使用递归的写法分享一下，网上较多的递归算法就不展示了

问题

输入 数组['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个 小时内。
以上是面试官的原问题

我的答案展示

目录结构（下面会按照这个顺序展示代码）

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"]];
}
///  根据数据构建二叉树模型
/// @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里面运行一下就了解了

结束