如何找到具有带有某种标签的后代叶节点的最低祖先？
给定一个有n个节点的根树，其中所有叶子都从一组标签中标记。构建一个数据结构，在给定叶节点a和标签l的情况下，可以找到a的最低祖先u，其中u至少有一个带有标签l的子代。
- 从叶a开始
- 检查
- 如果兄弟姐妹有标签l，则查找a和该兄弟姐妹之间的最低共同祖先
- 否则，继续给父母
这具有时间复杂度O（n）和空间复杂度O（n）。
对于线性空间复杂度，有没有更快的方法？也许通过某种方式对树进行预处理？l和a不是固定的，因此预处理必须灵活。
最低的共同祖先可以在常数时间内使用RMQ通过欧拉旅行找到。
请记住，树不是以任何方式平衡或排序的。
共有2个答案
这是一个时间复杂度为O（log（n）^3，空间复杂度为O（n log（n））的解。
让L成为您在欧拉路径上遇到的标签列表。您使用此列表构建一个段树，并在树的每个节点中存储出现在相应段中的标签集。然后您可以通过段树中的范围查询检查O（log（n）^2）时间，如果标签出现在子树中。
要找到正确的父母，你可以做二分搜索法。例如类似于二进制提升的东西。这将增加log(n)的另一个因子。
所以，现在我找到了一个更好的解决方案：
想法如下：欧拉路径中出现的越远的两个节点，它们的LCA越高。即index（a）
这意味着您只需计算路径中带有标签l的a和a之后的第一个节点的LCA，以及路径中带有标签l的a和a之前的最后一个节点的LCA。
其中之一将给出问题的最佳解决方案。
要有效地找到这两个索引，请为每个标签创建一个索引列表，并在O（log n）中执行二分查找。
存储器复杂度为O（n）。
-
问题内容： 如何使用BeautifulSoup搜索仅包含我要搜索的属性的标签？ 例如，我要查找所有标签。 如下代码： 获取我想要的所有数据，还获取具有该属性的所有标签 我也试过了： 这什么也不返回（可能是由于正则表达式不好） 我想知道在BeautifulSoup中是否有一种方法可以说“查找唯一属性为”的标签 *例如，如果HTML文档包含以下标记，则为 *UPDATE ： 我只希望第一个标签（）返回
-
我有以下树结构： 其中每个节点最多有一个父节点，但可以有多个子节点。我试图找到两个没有任何子节点(node1和node2)的最低共同祖先。 这是我当前的代码： 这段代码并不总是起作用，我不知道为什么。
-
68.1 二叉查找树 题目链接 Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree 解题思路 在二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 // java public TreeNode lowestCommonAncestor
-
我想使用py2neo的OGM来表示从一个节点类型到两个节点类型的关系。 这段关系的“结束”应该指向一辆车，而不是一栋房子。但显然py2neo并不关心那么多，而是像预期的那样将所有东西都存储在数据库中：一个人、一辆车和一栋房子通过拥有关系连接起来。 现在的问题是使用上面的类来检索节点和关系。当节点属性正确加载时，关系不是： 这导致： 此行为与类对象一致。 我如何在py2neo.ogm中用同一个类建模
-
我试图找到DOM中紧跟在前一个文本节点之后的文本节点的xpath--但它们不是兄弟，它们的xpath关系可能会改变。 我使用祖先和后代是因为uniqueID和text以及uniqueID和$amount之间的元素数量发生了变化。 我的最佳猜测（这不起作用）：//text（）[contains（.,“$”）][祖先：：div[1]//*[text()[contains（.,“uniqueText”）
-
在纯JavaScript中，如何找到最接近具有特定类的树的元素的祖先？例如，在这样的树中： 然后我想要，如果我在上尝试这个并搜索。