Блог

Мне нужно создать рекурсивный метод, который принимает в качестве параметра корневой узел двоичного дерева поиска. Затем этот рекурсивный метод вернет значение int общего количества внутренних узлов во всем двоичном дереве поиска.

Это то, что у меня есть до сих пор:

 int countNrOfInnerNodes (Node node) {
    if(node == null) {
       return 0;
    }
    if (node.left != null amp;amp; node.right != null){
       return 1;
    }
    return countNrOfInnerNodes(node.left) countNrOfInnerNodes(node.right)
    }
 }
 

Есть ли лучший способ? Я также пытался найти итеративное решение.

Исправлен рекурсивный метод:

 int countNrOfInnerNodes (Node node) {
    if(node == null) {
       return 0;
    }

    if (node.left == null amp;amp; node.right == null) {
       // not an inner node !
       return 0;
    } else {
       // the number of inner nodes in the left sub-tree   the number of inner
       // nodes in the right sub-tree, plus 1 for this inner node
       return countNrOfInnerNodes(node.left)   countNrOfInnerNodes(node.right)   1;
    }
}
 

Вот итеративный метод:

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

    Stack<Node> nodesToCheck = new Stack<Node>();

    nodesToCheck.push(node);
    int count = 0;

    while (!nodesToCheck.isEmpty()) {
        Node checkedNode = nodesToCheck.pop();
        boolean isInnerNode = false;

        if (node.left != null) {
            isInnerNode = true;
            nodesToCheck.push(node.left);
        }

        if (node.right != null) {
            isInnerNode = true;
            nodesToCheck.push(node.right);
        }

        if (isInnerNode)
            count  ;
    }

    return count;
}