java - 如何计算只有一个子节点的二叉树的节点数？

Question

我实现了以下功能:

public int count(Node n) {
    if (n == null) {
        return 0;
    } else if (n.left == null && n.right != null) {
        return 1 + count(n.right);
    } else if (n.left != null && n.right == null) {
        return 1 + count(n.left);
    }
    return 0;
}

问题是当我用以下方式调用它时:

System.out.println(tree.count(tree.root));

它只打印根的值。我做错了什么？

Answer 1

您的代码似乎同时具有实例方法和静态方法的元素，这有点令人困惑。选择一种，并在类似方法中保持一致。最简单的方法是使用按位异或 ^(如果两个表达式中恰好一个为 true，则返回 true )

这是一个静态方法。使用Node.countNonBranchingNodes(tree)调用:

public static int countNonBranchingNodes(Node n) {
    if (n == null) return 0;
    return (n.left != null ^ n.right != null ? 1 : 0) +
           countNonBranchingNodes(n.left) +
           countNonBranchingNodes(n.right);
}

如果您想要实例方法版本，请使用tree.countNonBranchingNodes()调用它:

public int countNonBranchingNodes() {
    int count = left != null ^ right != null ? 1 : 0;
    if (left != null) count += left.countNonBranchingNodes();
    if (right != null) count += right.countNonBranchingNodes();
    return count;
}