计算树中的左子节点

Question

我应该实现一个递归方法来计算左子树节点的数量.到目前为止我的代码是:

private int countLeftNodes(IntTreeNode node){
    int c = 0;
    if (node != null){
        c = 1 + countLeftNodes(node.left);
        countLeftNodes(node.right);
    }

    return c;
}

它返回的数字远小于应有的数字.我有一种感觉,我的遍历已关闭,因为它似乎只计算左边的子节点,然后终止.当我在大小为16的IntTree上调用此方法时,我应该得到8个左子节点,7个右子节点和一个根,但我得到4个左子节点.

Answer 1

您永远不会计算右侧树中的左侧节点.

private int countLeftNodes(IntTreeNode node)
{
    int c = 0;
    if (node.left != null)
    {
        c += 1 + countLeftNodes(node.left);
    }
    if(node.right != null)
    {
        c += countLeftNodes(node.right);
    }

    return c;
}