美文网首页程序员
二叉树和iOS层级中找到最近公共子节点(视图)

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

作者: 李周 | 来源:发表于2020-06-07 19:55 被阅读0次

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

百度百科中最近公共祖先的定义为:“对于有根树 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;
 }

相关文章

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

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个...

  • 0236-二叉树的最近公共祖先

    二叉树的最近公共祖先 方案一 在二叉树中来搜索p和q,然后从路径中找到最后一个相同的节点即为父节点,我们可以用递归...

  • 小米-基础算法-最近公共祖先

    给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。两个节点的最近公共祖先,是指两个节点的所有父...

  • 算法—— 最近公共祖先 III

    给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。两个节点的最近公共祖先,是指两个节点的所有父...

  • 二叉树-最近的公共祖先

    已知二叉树,求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u,满足在树上最低...

  • 最近公共祖先系列

    最近公共祖先I 描述: 给定一棵二叉树,找到两个节点的最近公共父节点 (LCA)。最近公共祖先是两个节点的公共的祖...

  • LintCode 578. 最近公共祖先 III

    题目描述 给一棵二叉树和二叉树中的两个节点,找到这两个节点的最近公共祖先LCA。 两个节点的最近公共祖先,是指两个...

  • iOS11 table左滑按钮自定义

    1.UITableView视图层级 iOS8-10 :左滑视图层是UITableViewCell的子视图,UITa...

  • UIToolbar 子视图无响应问题

    在UIToolbar上addSubView添加子视图时,子视图无法响应,经测试在iOS 11上复现查看视图层级关系...

  • 二叉树概念小谈

    二叉树概念 二叉树是一个层级的数据结构,每一个二叉树都包含头节点或者子节点,并且二叉树的子节点最多是两个,如下几个...

网友评论

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

    本文链接:https://www.haomeiwen.com/subject/ifkhtktx.html