找到给定的两个节点的共同祖先的算法 [英] Algorithm to find common ancestor of two nodes given

问题描述

如果给我两个节点和树的根.如何找到两个节点的共同祖先?

If two nodes and root of tree are give to me. How to find the common ancestor of two nodes?

推荐答案

这是我发现对 LCA 有用的 Python 实现:-

Hi here's a python implementation that I found useful for LCA :-

class BST(object):
def __init__(self, val=None, right=None, left=None):
    self.val = val
    self.right = right
    self.left = left
    return None

def __nonzero__(self):
    return self.val is not None

def insert(self, item):
    if not self:
        self.val = item
    elif item < self.val:
        if self.left:
            return self.left.insert(item)
        else:
            self.left = BST(val=item)
    elif item > self.val:
        if self.right:
            return self.right.insert(item)
        else:
            self.right = BST(val=item)
    return None

def lca(self, m, n):
    if n < self.val:
        return self.left.lca(m, n)
    elif m > self.val:
        return self.right.lca(m, n)
    else:
        return self.val


if __name__ == "__main__":
b = BST()
for k in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    b.insert(k)
for pair in [(4, 7), (4, 10), (1, 4), (1, 3), (3, 6)]:
    print b.lca(*pair)

这篇关于找到给定的两个节点的共同祖先的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！