1 
class TreeNode {
    TreeNode parent;
    TreeNode left;
    TreeNode right;

    // other data fields omitted - not relevant
}

你有两个节点p，q你如何找到最低的共同祖先？（假设它们都属于一棵非常大的树）

您没有参考树的根。

最有效的方法是什么？到目前为止，我唯一的想法是

(1) 选择一个节点 p（不管哪个）

(2)搜索p的左子树，如果看到q，返回p

(3) else搜索p的右子树，如果看到q，返回p

(4) else 上一级 parent 查找不包含 p 的子树，如果找到 q，则返回 parent

(5) else，再上一级，重复(4)（搜索不包含这个父节点的子树）

这似乎效率极低。有更好的算法吗？

4

1 回答 1

1

您对允许使用的 RAM 数量有极端限制吗？如果没有，我会提出这样的建议：

visited_nodes = {}    // something like a HashMap, with O(1) insert and retrieval
node1 = p
node2 = q

while True:
    if node1 == null and node2 == null:    // the nodes don't seem to be in same tree
        return null    // or failure or anything like that

    if node1 is not null:
        if node1 in visited_nodes:    // node1 must be lowest common ancestor
            return node1
        else:
            visited_nodes.insert(node1)    // remember that we've seen this node
            node1 = node1.getParent()

    if node2 is not null:
        if node2 in visited_nodes:    // node2 must be lowest common ancestor
            return node2
        else:
            visited_nodes.insert(node2)    // remember that we've seen this node
            node2 = node2.getParent()

直观的想法如下。我们同时从两个节点开始。在循环的每一次迭代中，我们从两个节点都上移一步。每当我们看到一个节点时，我们就把它放在我们的地图中（它应该有 O(1) 的插入和检索/检查它是否已经在那里）。当我们遇到已经放入地图的节点时，这一定是我们的解决方案。

此代码的运行时间不应超过max(d_p, d_q)迭代，其中d_p和d_q分别表示树中的深度级别p和q。如果两个节点碰巧都非常靠近根，这将是一个很大的优势。这也意味着代码甚至适用于无限树（而您的解决方案会陷入无限循环）。

于 2017-12-21T14:33:07.460 回答