Блог

У меня есть дерево, в котором некоторые узлы имеют определенную характеристику. Я хочу подсчитать количество узлов в дереве, которые имеют эту характеристику, используя алгоритм, подобный DFS. Однако я неправильно использую возвращаемые значения. Если найден узел с этой характеристикой, я хочу, чтобы какой-то счетчик увеличивался, в противном случае счетчик не увеличивается.

Это довольно просто, но я не смог реализовать это должным образом.

     private int dfs(Node node) {

    for(Node n: node.children){ 
        if(n != null amp;amp; n.someOtherCondition){
            return 1   dfs(n);
        }
    }
    return 0;
    }
  

Вы должны накапливать результаты рекурсивного вызова DFS для всех дочерних элементов вместо возврата к первому.

 private int dfs(Node node) {
  int count = 0;

  for(Node n: node.children){ 
    if(n != null amp;amp; n.someOtherCondition){
        // check if the child-node has children
        if(n.children.length > 0){
          count = count   dfs(n); // recursively count the grandchildren aswell
        }
        count = count   1; // add one because we meet the condition once on this level
    }
  }

  return count;
}
  

Не возвращайтесь сразу, когда найдете соответствующий узел: посчитайте их и вернитесь в конце.

 private int dfs(Node node) {
  int count = 0;
  for(Node n: node.children){ 
    if(n != null amp;amp; n.someOtherCondition){
      count  = 1;       // Count this node.
      count  = dfs(n);  // Count this node's children.

      // Alternatively: count  = 1   dfs(n); split up for clarity.
    }
  }
  return count;
}
  

Обратите внимание, что вы на самом деле не проверяете условие для параметра node , поэтому вы фактически не будете считать узел, с которого вы начинаете, если это соответствует условию; в зависимости от вашего приложения, это может быть или не быть необходимым. Если вы действительно хотите посчитать и этот узел:

 private int dfs(Node node) {
  if (node == null) return 0;

  int count = node.someOtherCondition ? 1 : 0;

  for(Node n: node.children){ 
    count  = dfs(n);
  }

  return count;
}
  

Короткий и приятный:

 private int dfs(Node node) {
    int count = node.someOtherCondition ? 1 : 0;
    for (Node child : node.children)
        if (child != null)
            count  = dfs(node);
    return count;
}