计算树中的左子节点数

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 个右子节点和 1 个根，但我得到的是 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;
}

Answer 2

要计算左子节点，您可以执行以下操作：

private int countLeftNodes(IntTreeNode node) {

    // no tree no left-child nodes      
    if(node == null) {
       return 0;
    }

    // left-child count of current node.
    int c = 0;

    // does the current node have a left-child ?
    if (node.left != null){
      c = 1;
    }

    // return left-child count of current node +
    // left-child count of left and right subtrees
    return c + countLeftNodes(node.left) + countLeftNodes(node.right);
}

Answer 3

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

    return c;
}

Answer 4

最容易检查的地方是父级。

private int countLeftNodes(IntTreeNode node){

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

    return c;
}

Answer 5

使用递归时我最喜欢的风格是使用某种包装函数，其中主方法调用另一个执行繁重工作的函数：

private int countLeftNodes(IntTreeNode node){
   int totalCount = reallyCountLeftNodes(IntTreeNode node, 0); 
   return totalCount;
}

private int reallyCountLeftNodes(IntTreeNode n, Int sum){
    if (n.left == NULL && n.right == NULL){  //check if we've hit rock bottom
        return sum;
    } else if (n.left == NULL) { //if the node's left is nil, go right
        reallyCountLeftNodes(n.right, sum++);   
    } else {
        reallyCountLeftNodes(n.left, sum++);  // Going as far left as possible!
    }
}

注意主函数如何调用另一个函数。我发现这种风格更干净、更容易理解。另外，第二个函数有一个计数变量供您使用。