2 
# 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 类对其进行硬编码，但我想使用上面提到的命令行输入来构建树。

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

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

我正在尝试学习 LCA，因此非常感谢以最简单的方式在正确方向上提供一些帮助。

4

1 回答 1

1

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

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

  • 检查父母是否在树中。如果父母存在，请检查是否已经存在左孩子。
    • 如果存在左孩子，则让孩子成为父母的右孩子。
    • 如果左孩子不存在，则让孩子成为父母的左孩子。
  • 如果父节点不存在于树中，则意味着这对
    • 是第一个被读取的，因此必须将父级设为根，或者
    • 包含无效的父级。

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
于 2016-09-11T14:33:30.177 回答