Scott's Blog

学则不固, 知则不惑

0%

算法题:N叉树的最近公共祖先

发表于 分类于 阅读次数： Valine：

给定一个树（非二叉树）, 找到该树中两个指定节点的最近公共祖先。（树使用key为子级，value为父级的字典结构存储。

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

tree 定义：

1
2
3
4
5
6
7
8
9
10
11
12
tree = {1:None, 2:1, 3:1,4:2,5:2,6:2,7:3,8:3,9:4,10:4,11:7}
# 输入
p = 5
q = 1
# 输出：1
# 解释：节点 5 和节点 1 的最近公共祖先是节点 1

# 输入：
p = 9
q = 6
# 输出：2
# 解释：9 的祖先是4，不是6的祖先，往上走，2则是

递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def get_common_ancestor(tree, p, q):
    # if it's a empty tree, or givin nodes not in dict
    if not tree or p not in tree or q not in tree: return

    # root node
    root = [k for k,v in tree.items() if v is None][0]

    # if any givin nodes is root node
    if tree.get(p) is None or tree.get(q) is None: return root

    # recursive helper function
    def recursive(tree, rp, rq):
        if rp == tree.get(rq): return rp  # p is children of q
        if rq == tree.get(rp): return rq  # q is children of p
        if rq == p: return p              # q move up, equal p then p
        if rp == q: return q              # p move up, equal q then q
        if tree.get(rp) == tree.get(rq):  # p,q moved to root
            return tree.get(rp)
        return recursive(tree, tree.get(rp), tree.get(rq))

    return recursive(tree, p, q)