如何在非二叉树的一次递归搜索中获得节点的深度 [英] How to get depth of a node in one recursive search in non-binary tree

问题描述

根据>以非二进制方式递归搜索节点树，我知道如何实现递归搜索，但是如何获得该节点的深度？

According to Recursive search for a node in non-binary tree, I know how to achieve the recursive search but how can I get the depth of this node?

我认为我应该为每个递归添加一个计数器但是我不知道应该在哪里添加此计数器。....

I think I should add a counter for every recursion but I have no idea where I should add this counter.....

谢谢

推荐答案

以下是带有注释的部分代码：

Here is the partial code with comments:

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;
    }
}

这篇关于如何在非二叉树的一次递归搜索中获得节点的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！