java - 在二叉搜索树中计算 "sticks"(有一个 child 的节点)？

Question

所以我正在使用二叉搜索树，而我遇到问题的一种方法是名为 stickCt 的方法，它基本上会计算树中 Twig 的数量并返回数量。为了让它成为一根棍子，它必须有一个 null 和一个非 null 的 child 才能被认为是一根棍子，我已经完成了我的代码并且它符合要求但是我一直得到 0 作为我的返回值，我不知道出了什么问题我试过四处移动东西，但似乎没有任何帮助，将不胜感激。顺便说一句，我递归地做这件事，这是代码:

// The number of nodes with exactly one non-null child
//driver

public int stickCt () {

    return stickCt(root);
}

private static int stickCt (IntNode T) {
    int num;

    //easiest case
    if (T == null) {
        num = 0;
    }
    //if the left child is null and the right child is not null
    else if (T.getLeft() == null && T.getRight() != null) {
        num = stickCt(T.getRight()) + 1;
    }
    //if right child is null and left side is not null
    else if (T.getRight() == null && T.getLeft() != null) {

        num = stickCt(T.getLeft()) + 1;
    }
    //recursive part
    else {
        num = stickCt(T.getLeft()) + stickCt(T.getRight());

    }
    return num;

}

Answer 1

问题在于，您应该返回对每个节点上的棍子进行计数的总和，但您只返回棍子的当前值。您可以这样重写该方法:

private static boolean onlyOneIsNull(IntNode node1, IntNode node2) {
    return (node1 != null && node2 == null)
           || (node1 == null && node2 != null);
}

private static int stickCt(IntNode T) {
    //easiest case
    if(T==null) {
        return 0;
    }
    //evaluating if I'm a stick
    int num = 0;
    if (onlyOneIsNull(T.getLeft(), T.getRight())) {
        num = 1;
    }
    //stickCt already takes care of null nodes, no need to add a null validation for nodes
    //need to return the number of sticks from left node and right node
    return stickCt(T.getLeft()) + stickCt(T.getRight()) + num;
}