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

2018-10-08  本文已影响0人  旭仔_2e16

算法思想:递归

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。

上一篇下一篇

猜你喜欢

热点阅读