如何在一棵非二叉樹的遞歸搜索中獲得一個節點的深度

Question

根據Recursive search for a node in non-binary tree，我知道如何實現遞歸搜索，但我怎樣才能得到這個節點的深度？

我想我應該添加一個計數器，每遞歸，但我不知道在哪裏，我要補充這個計數器.....

謝謝

Answer 1

下面是部分代碼註釋：

public class Tree 
{ 
    private Node root; 

    public int findDepth(int searchNodeValue) { 
     List<Node> nodesAtCurrentLevel = Collections.singletonList(root); 

     return recursiveSearch(0, searchNodeValue, nodesAtCurrentLevel); 
    } 

    public int recursiveSearch(int level, int searchNodeValue, List<Node> nodesAtCurrentLevel) { 
     List<Node> nodesAtNextLevel = new ArrayList<Node>(); 

     // Check if searchNode matches any node at current level 
     for (Node node : nodesAtCurrentLevel) { 
      // If it matches, we have found the node, return current level 
      if (node.getValue() == searchNodeValue) { 
       return level; 
      } 

      // Add children of all nodes at current level in nodesAtNextLevel 
      if (node.hasChildren()) { 
       nodesAtNextLevel.addAll(node.getChildren()); 
      } 
     } 

     // searchNode is not found at current level, increment level and continue search at next level if next level exists in tree 
     if (!nodesAtNextLevel.isEmpty()) { 
      return recursiveSearch(level + 1, searchNodeValue, nodesAtNextLevel); 
     } 

     // We have traversed entire tree. Node not found. Return -1 
     return -1; 
    } 
} 

class Node 
{ 
    private int value; 

    private List<Node> children = new ArrayList<Node>(); 

    public Node(int value) { 
     this.value = value; 
    } 

    public boolean hasChildren() { 
     return children.isEmpty(); 
    } 

    public int getValue() { 
     return value; 
    } 

    public List<Node> getChildren() { 
     return children; 
    } 
} 

Answer 2

編輯

- 有遞歸函數獲取輸入級別。從0/-1開始。返回一個對象;該對象具有節點AND級別。遞歸函數的每一次遞增傳入的級別並將其設置在返回對象中。

- 將級別傳遞給遞歸函數。從0/-1開始。維護一個全局變量（或一個變量，該變量被定義爲非局部於該函數，以便在該函數的每次迭代中都訪問同一個變量;即變量不在堆棧上，而在堆上）我希望這件事很簡單Java並不需要進一步解釋）。在遞歸函數開始時將其設置爲（1 +傳入級別）。這不會是線程安全的。

//原始答案的想法是作爲參考傳遞給關卡，並在遞歸函數中增加它。顯然這在Java中很乏味。