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

我实现了以下功能：

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

它只显示根的值。我究竟做错了什么？

最佳答案

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

这是一个static方法。使用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;
}