二叉树算法之1-计算二叉树第k层节点个数

算法思想：递归

public int getCount(Node node, int k){
  if(node==null){
    return 0;
  }
  if(k==0){
    return 1;
  }
  return getCount(node.left, k-1) + getCount(node.right, k-1);
}

算法解析：把k作为计数器通过参数递归传递，递归的过程中不断减1，直到k==0时说明找到一条从根节点到该k(k从0开始)层节点的路径，计作1条路径，也就是一个节点，不断展开左树和右树，最后就是k层节点数的和，即第一层计算结果由第二层得到，第二层计算结果由第三层得到，依次类推，直到第k层计算出最终结果。需要注意的是递归终止条件node==null，说明该条路径深度小于k。