计算树中的左子节点

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

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个左子节点。

来源

2011-03-21 Shane

您没有添加右侧子节点的左侧节点。 – Zimbabao 2011-03-21 18:01:52

您从不计算右侧树中的左侧节点。

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

来源

2011-03-21 18:00:21 Endophage

我已经尝试过，但是它会返回整个树中的节点数量。 – Shane 2011-03-21 18:01:58

是的，我可以看到为什么，一分钟，我会修复 – Endophage 2011-03-21 18:03:00

@Shane现在应该工作。它基本上做了一个前瞻，并添加一个，如果左边的孩子不是空的。 – Endophage 2011-03-21 18:05:54

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

来源

2011-03-21 18:04:05 Zimbabao

要计算左子节点，你可以这样做：

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

来源

2011-03-21 18:05:10 codaddict

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

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

来源

2011-03-21 18:10:14 Zak

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

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! 
    } 
}

通知的主要功能是如何调用另一个。我觉得这种风格更清晰，更易于理解。此外，第二个函数有一个计数变量供您使用。

来源

2011-03-24 01:15:22

计算树中的左子节点

回答

相关问题