平衡树中的节点数

Question

所以我提出了一个有趣的问题,看看是否有一种有效的解决方法.所以基本上有一个平衡的二叉树,其中保存了id号(它不是bst所以没有正式的安排).您有大量的查询来查找有多少节点.保证对于每个节点E,左子树将具有与该节点E上的右子树一样多或多一个节点.请求程序找出有多少节点的最佳方式是什么？例如给出这样的树:

          1
      4      2
  3

该程序将提供以下输出:

 Query: 1
 Response: 4 2
 Query: 4
 Response 3
 Query: 3
 Response: 0 0 
 Query: 2
 Response: 0 0
 Answer: 4

Answer 1

int countnodes(ele,count)
{
 if(ele.right != null)
   {
      count += countnodes(ele.right,0);
   }
  if(ele.left != null)
  {
     count += countnodes(ele.left,0);
  }
  return count++; //got to count this node
}