寻找两个view的最近公共view

我在唐巧的微信里看到这道题的第二天，就在面试里被问到了，实话说我答的并不好，所以整理一下。

题目：找出两个 UIView 的最近的公共 View，如果不存在，则输出 nil 。

首先我们写一个函数去找到一个View的所有父view，并返回一个数组，这个数组存储着这条链上的所有view。

-(NSArray*)superViews:(UIView *)viewA{

    if (viewA == nil) {

        return @[];

    }

    NSMutableArray* superViewsArray = [NSMutableArray array];

    if (viewA != nil) {

        [superViewsArray addObject:viewA];

        viewA = viewA.superview;

    }

    return [superViewsArray copy];

}

这样我们就可以得到两个view对应的两个数组了，找最近的公共view其实就是找这两个数组的第一个公共节点。

如果遍历第一个数组然后把第一个数组里的每一个元素和第二个数组里的每一个元素比较,时间复杂度就是n2。

我们可以利用NSSet的性质，在O(1)时间内找到一个元素，这样时间复杂度就是n。

但是增加了存储空间。

//我们把两个view的所有父view都存在了数组里，那么想要比较两个view最近的根节点其实就是从头比较两个数组，看第一个公共元素是什么，就是我们要找的第一个公共父view啦！

-(UIView*)commonView:(UIView*)viewA andView:(UIView*)viewB{

    NSArray* superViewA = [self superViews:viewA];

    NSArray* superViewB = [self superViews:viewB];

    NSSet* view2Set = [NSSet setWithArray:superViewB];

    UIView* resultView = [[UIView alloc] init];

    for (NSUInteger i =0; i<view2Set.count; i++) {

        if ([view2Set containsObject:superViewA[i]]) {

            resultView = superViewA[i];

            return resultView;// 找到了就马上返回，不要再继续找了

        }

    }

    return nil;

}