Как подсчитать узлы структуры данных, если у ребенка несколько родителей?

Question

Мне нужна помощь с назначением в java ... итак, у меня есть класс TreeNode, который выглядит следующим образом ... так нас просили сделать это, поэтому мне не разрешено его менять .

class TreeNode{
int data;
TreeNode leftNode;
TreeNode rightNode;
public TreeNode(int data) {
     this.data=data;
}

}

Проблема в том, что мне нужно создать метод int getNumOfNodes(TreeNode t), который будет возвращать количество узлов в структуре. Дело в том, что я не могу понять, как считать узел со значением 9 только один раз, так как я пытаюсь использовать рекурсию для левого и правого поддерева, и поскольку у этого указанного узла c есть два родителя, он считается дважды ... Любые идеи?

Я пытаюсь создать эту структуру (я пытаюсь объяснить это, так как я не могу опубликовать пи c)

           5
         /  \
        7    12
         \  /  \
          9      2

вот что я пытался

 int getNumOfNodes (TreeNode t){


    if(t==null)
        return 0;


    return 1 + getNumOfNodes(t.leftNode) + getNumOfNodes(t.rightNode);
}

Answer 1

Вы можете сначала собрать / найти все TreeNode объекты и поместить их в Set. Поскольку Set не может иметь дубликатов, вы добавляете узел только один раз, даже если встречались с ним более одного раза. Вы можете написать вспомогательный метод следующим образом:

private static Set<TreeNode> findAllNodes(TreeNode node) {
    Set<TreeNode> nodes = new HashSet<TreeNode>();
    nodes.add(node);
    if (node.leftNode != null) {
        Set<TreeNode> leftNodes = findAllNodes(node.leftNode);
        nodes.addAll(leftNodes);
    }
    if (node.rightNode != null) {
        Set<TreeNode> rightNodes = findAllNodes(node.rightNode);
        nodes.addAll(rightNodes);
    }
    return nodes;
}

(непроверенный псевдокод)

После этого вы можете просто позвонить size(), чтобы узнать, сколько узлов вы

Set<TreeNode> allNodes = findAllNodes(t);
return allNodes.size();

Имейте в виду, что этот псевдокод не работает для графов с циклами.