java - 使用 Stack 跟踪一般树中节点的所有祖先

Question

我已经创建了使用堆栈跟踪一般树中节点的祖先的函数，但它不起作用，需要帮助 (John，1925)和(Fred，1900)的共同祖先:(弗雷德，1900)(John，1925)和(Fred，1953)的共同祖先:(约翰，1925)，(弗雷德，1900)

public void Find_FamilyTree(Node node,Node toFind,Stack<Node> st)
{

    st.push(node);
    if(node.getData().getName().equals(toFind.getData().getName()))
    {
        st.pop();
    }

如果节点是叶节点，则弹出

    if(node.getChildrenCount()==0)
    {
        st.pop();
    }


    for(Node nodes:node.getChildren())
    {
        Find_FamilyTree(nodes,toFind,st);
    }

}

Answer 1

很简单。

仅使用 DFS 来跟踪树并在进入/离开节点时推送/弹出节点。只有找到该节点才立即返回，然后您就得到了祖先的堆栈。

示例如下:

public boolean Find_FamilyTree(Node node,Node toFind,Stack<Node> st) {

    if(node.getData().getName().equals(toFind.getData().getName()))
    {
         return true;
    }
    st.push(node);

    for(Node nodes:node.getChildren())
    {
        if(Find_FamilyTree(nodes,toFind,st)){
           return true;
        }
    }

    st.pop(node);
    return false;

  }