二叉树和iOS层级中找到最近公共子节点(视图)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

LeetCode:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

解题思路分析

首先对于二叉树而言，某个节点本身也称为该节点的祖先。其次两个节点的公共祖先一共应该有三种情况:

① q是p的子节点，那么最近公共祖先为 p

② p是q的子节点，那么最近公共祖先为q

③ p和q分别为某个节点的左右节点，那么最近公共祖先为该节点

def lowestCommonAncestor(root, p, q):
    def helper(root):
        if not root or root == p or root == q: return root
        left = helper(root.left)
        right = helper(root.right)
        if not left and not right: return
        if not left: return right
        if not right : return left
        return root
    return helper(root)

升级思路

关于二叉树的最近公共祖先，也能想到在iOS中如何找到两个view的最近superView。

首先，拿到当前view的所有superView的集合

 NSMutableArray *arr = [NSMutableArray array];
    while (cls) {
        [arr addObject:cls];
        cls = [cls superview];
    }
    return arr;

其次，如果找到两个集合中最近的superView，那么从该节点开始后面的数量一致，根据这个规律可知：

① viewA 在上层，viewB在下层，那么viewA.count >viewB.count

image

repeat_count = Min(viewA.count， viewB.count)
start_posA = viewA.count - repeat_count
start_posB = viewB.count - repeat_count

② 按照repeat_count从 MinCount - 0的顺序进行查找

while (repeat_count > 0) {
  PASS
}

③ 具体实现

- (UIView *)commonSuperViewBetween:(UIView *)cls1 and:(UIView *)cls2 {
    
    NSArray *arr1 = [self getSuperViewArray:cls1];
    NSArray *arr2 = [self getSuperViewArray:cls2];
    
    NSUInteger count = MIN(arr1.count, arr2.count);
    
    while (count > 0) {
        
        UIView *view_inA = [arr1 objectAtIndex:arr1.count - count];
        UIView *view_inB = [arr2 objectAtIndex:arr2.count - count];
        
        if (view_inA == view_inB) {
            return view_inA;
        }
        count --;
    }
    return nil;
 }