python - 最下位の共通祖先、コマンドライン入力からツリーを構築する方法は?

Question

# Python program to find LCA of n1 and n2 using one
# traversal of Binary tree

# def build_graph():
#     n = input()
#     ex1, ex2 = raw_input(), raw_input()
#     d = {}
#     for i in xrange(n-1):
#         e1, e2 = map(str, raw_input().split())

#         if e1 not in d:
#             node = Node(e1)
#             node.left = Node(e2)
#             d.update({e1:node})
#         if e1 in d:
#             d[e1].right = Node(e2)

#     # for i in d.values():
#     #     print i.key, i.left.left.key, i.right.key
#     print d.get(next(d.__iter__()))
#     return d

def build_graph():
    l = []
    n = input()
    ex1, ex2 = raw_input(), raw_input()
    for i in xrange(n-1):
        e1, e2 = map(str, raw_input().split())

        node1 = Node(e1)
        node2 = Node(e2)

        if len(l) > 0:
            if node1 not in l:
                node1.left = node2
                l.append(node1)
            if e1 in d:


# A binary tree node
class Node:
    # Constructor to create a new tree node
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

# This function returns pointer to LCA of two given
# values n1 and n2
# This function assumes that n1 and n2 are present in
# Binary Tree
def findLCA(root, n1, n2):
    # print graph
    # if type(graph) is dict:
    #     root = graph.popitem()
    #     root = root[1]
    # else:
    #     root = graph
    # Base Case
    if root is None:
        return root

    # If either n1 or n2 matches with root's key, report
    #  the presence by returning root (Note that if a key is
    #  ancestor of other, then the ancestor key becomes LCA
    if root.key == n1 or root.key == n2:
        return root

    # Look for keys in left and right subtrees
    left_lca = findLCA(root.left, n1, n2)
    right_lca = findLCA(root.right, n1, n2)

    # If both of the above calls return Non-NULL, then one key
    # is present in once subtree and other is present in other,
    # So this node is the LCA
    if left_lca and right_lca:
        return root

    # Otherwise check if left subtree or right subtree is LCA
    return left_lca if left_lca is not None else right_lca

# Driver program to test above function

# Let us create a binary tree given in the above example
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.left.left.left = Node('F')
# root.left.left.right = Node('F')
build_graph() # not being used not but want to take input and build a tree
print findLCA(root , 'Hilary', 'James').key

コマンドラインでの入力は次のようになります。

6
D
F
A B
A C
B D
B E
E F

ご覧のとおり、Node クラスを使用してハードコードすることもできますが、上記のようにコマンド ライン入力を使用してツリーを構築したいと考えています。

入力形式: 最初の数字は、家族内の一意の人数です。そして、家族の中で選ばれた2人。D、F、および残りの行には、スペースで区切られた 2 人の名前が含まれています。AB は、A が B の上位にあり、B が E および D の上位にあることを意味します。簡単にするために、AB である最初のセット、A をツリーのルートと見なす必要があります。

root = Node('A')では、コマンド ラインから入力を読み取り、 、 などで実行できるのと同じツリーを構築するにはどうすればよいroot.left = Node('B')でしょうか?

私はLCAを学ぼうとしているので、最も簡単な方法で正しい方向に助けていただければ幸いです.