最低共同祖先，如何从命令行输入构建树？

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 class 对其进行硬编码，但我想如上所述使用命令行输入构建树。

输入格式：第一个数字是一个家庭中唯一成员的数量。并且，然后是一个家庭中的两个选定的人，即； D、F，然后其余行包含两个人的姓名，并带有 space 分隔符。 A B 表示，A 高级于 B，B 高级于 E 和 D 等。为简单起见，第一个集合是 A B，A 必须被视为树的根。

那么，我如何通过命令行读取输入并构建与我能够通过 root = Node('A')、root.left = Node('B') 等实现的相同的树？

我正在努力学习 LCA，因此非常感谢以最简单的方式向正确的方向提供帮助。

Answer 1

我建议您使用字典或其他方式来跟踪树的成员。

根据你构建树的方式，这就是我想出的：当你解析每个有序对时，

检查 parent 是否在树中。如果 parent 存在，检查是否已经存在左 child。
- 如果左 child 存在，则将 child 设为 parent 的右 child。
- 如果左 child 不存在，则将 child 设为 parent 的 left child。
如果 parent 不在树中，这意味着这对
- 是第一个被读取的，因此parent必须作为根，或者
- 包含无效 parent。

Python-ish 伪代码（没有错误处理）：

members = {}
for line in input:
    parent_key, child_key = line.split(' ')

    if parent_key not in members:
        # I'm assuming this will happen only for 
        # the first pair
        root = members[parent_key] = Node(parent_key)

    parent = members[parent_key]

    if parent.left is None:
        # If the child already exists, don't create a new one
        # You can change this and the next statement if this isn't what you want
        # This also assumes that the given child, if exists
        # is not already a child of any member 
        # If that can happen, you'll need to keep track of parents too
        parent.left = members.get(child_key, Node(child_key))
        members[child_key] = parent.left
    else:
        # Assuming that the parent will not have
        # a right child if we're here
        parent.right = members.get(child_key, Node(child_key))
        members[child_key] = parent.right

最低共同祖先，如何从命令行输入构建树？

Lowest common ancestor, how to build the tree from command line input?

python

algorithm

tree

binary-tree

lowest-common-ancestor