计算二叉树中叶节点的数量

Question

我想要计算叶子节点的数量:注意:不能使用全局/类级别变量我跟随算法,它工作正常.但我希望方法签名是

countLeaves(Node node)

我知道我可以重载methds并从1个args调用2 args方法sig,但是不想这样做.任何人都可以建议任何其他方法吗？

int countLeaves(Node node,int count){
        if(node==null)
            return 0;

        if(node.left==null && node.right==null){
            return 1+count;
        }else{
            int lc = countLeaves(node.left, count);
            int total = countLeaves(node.right, lc);
            return total;
        }
    }

Answer 1

int countLeaves(Node node){
  if( node == null )
    return 0;
  if( node.left == null && node.right == null ) {
    return 1;
  } else {
    return countLeaves(node.left) + countLeaves(node.right);
  }
}

你正在做与以前相同的事情,但我们只是说返回左右节点之和的结果,而不是保持当前计数.这些反过来直到他们击中基地.

Answer 2

您不需要传递count调用堆栈,只需从以下位置:

int countLeaves(Node node)
{
    if(node==null) {
        return 0;
    }
    if(node.left==null && node.right==null) {
        return 1;
    }
    return countLeaves(node.left) + countLeaves(node.right);
}