c++ - 打印二叉树中所有节点的祖先。我们可以用小于 O(n^2) 的时间复杂度来完成吗？

Question

这是打印二叉树中特定节点的祖先的标准算法，它需要 O(n) 的时间复杂度。

bool print(Node *node,int target){
    if(node==NULL)
       return false;
    if(node->target==target)
       return true;
    if(print(node->left)||print(node->right)){
       cout << node->data;
       return true;
    }
return false;
}

问题是我们是否需要打印所有节点 的所有祖先并将每个节点的祖先存储在一个数组中。时间复杂度是多少？我们能否做得比 O(n^2) 更好，即不遍历每个节点并找到祖先。如果可能的话，怎么做？

Answer 1

如果你想要一个 array 对应于树中的每个节点，那么你不能比 O(N²) 的最坏情况做得更好，因为所有的总大小数组是最坏的情况 O(N²) (在树中的每个节点最多有一个 child 的情况下)。如果您希望树在某种程度上是平衡的，这将减少到 O(N log N)。

可以通过共享数据实现O(N)构造，对每个节点使用链表而不是数组。实际上，这相当于为每个节点计算父链接，因为链表只是对父链接的遍历。但是您无法避免打印成本，因为当您打印出所有祖先链时，您将打印平均 O(N log N)/最坏情况 O(N²) 项。

父链接构建算法与您提供的算法基本相同:递归遍历树，将子节点的父链接设置为当前节点。要打印每个节点的祖先链，您可以在遍历树时使用父链接。