二叉树算法之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。