在二叉树中打印所有节点的祖先。我们可以用小于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

它可以在O(n*h)中完成，其中h是树的高度，通过执行DFS来跟踪当前打开的节点。

一个简单的类似于C++的伪代码可以是这样的：

void PrintAll(const Node& node) { 
    open = std::unordered_set<Node>; // empty hash set 
    PrintAll(node, &open); 
} 
void PrintAll(const Node& node, std::unordered_set* open) { 
    if (node == null) 
    return; 
    for (const Node& ancestor: open) 
    cout << ancestor<< "," << node; 
    open->add(node); 
    PrintAll(node.left, open); 
    PrintAll(node.right, open); 
    open->remove(node); 
} 

警告：在这里，我们不打印(node, node)（每个节点也是它本身的祖先）。如果我们想这样做，可以通过在打印循环之前添加node到open来轻松修复它。
此外，您可以使unordered_set只存储数据，而不是整个节点。

Answer 2

如果想对应的阵列到每个节点的树中，则可以不大于O（N ）最坏的情况下做比较好，因为所有阵列的总大小是最坏的情况下O（N ）（在树中的每个节点至多有一个孩子的情况下）。如果你期望树木有些平衡，这会降低到O（N log N）。

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

父链接构造算法与您呈现的算法基本相同：递归地遍历树设置子节点的父链接到当前节点。要打印每个节点的祖先链，可以在走树时使用父链接。

Answer 3

下面的代码将做的工作：

使用语言：Java的

// Algorithm for printing the ancestors of a Node. 
static boolean findAncestors(Node root, Node a) 
{ 
    if(root==null) 
    { 
     return false; 
    } 
    else if(root==a) 
    { 
     System.out.print("Printing ancestors of node " + a.data + " : " + a.data); 
     return true; 
    } 
    else 
    { 
     boolean var=false; 
     var=findAncestors(root.left, a); 
     if(var) 
     { 
      System.out.print(", " + root.data); 
      return true; 
     } 

     var=findAncestors(root.right, a); 
     if(var) 
     { 
      System.out.print(", " + root.data); 
      return true; 
     } 

    } 
    return false; 
}