c++ - 在树中检查给定节点是否是另一个节点的祖先

我有一个问题-如果给定2个节点(A，B)是B的祖先，我需要回答这个问题。我知道可能的解决方案是获取进入节点的时间和离开节点的时间。基于此，我可以快速计算关系。如何使用DFS获取那些无法通过重复实现的“时间戳”？

我不是算法和C++方面的专家，这就是为什么我要问。

最佳答案

我找到了一种方法。如果您的树在邻接列表中，那么您可以进行预处理。对于每个节点，您需要在输入值和在DFS期间离开值时为其分配值，然后可以在固定时间内对其进行检查:

if (timeIn[b] >= timeIn[a] && timeIn[b] <= timeOut[a]) {
   printf("YES\n");
}
else {
   printf("NO\n");
}

如果a是b的祖先。

DFS:

// INITIALIZE VARs
int time = 0;
stack<int> stackOfChildNodes;
// put root of tree
stackOfChildNodes.push(first);
// go with DFS
while (!stackOfChildNodes.empty()) {
    int current = stackOfChildNodes.top();
    stackOfChildNodes.pop();
    // if node was not visited (time is not set)
    if (timeIn[current] == -1) {
        timeIn[current] = time; // node visited
        time++; // increase time to go further
        stackOfChildNodes.push(current); // include node in processing to leave it in future
        int child = children[current];
        // add descendants to process them
        while (child != 0) {
            stackOfChildNodes.push(child);
            child = descendants[child];
        }
    }
    // if node was visited, so we gonna leave him now
    if (timeIn[current] != -1) {
        timeOut[current] = time-1;
    }
}