求二叉树第K层的节点数和二叉树第K层的叶子节点数，递归方式和非递归方式。
1、二叉树定义
typedef struct BTreeNodeElement_t_ {
void *data;
} BTreeNodeElement_t;
typedef struct BTreeNode_t_ {
BTreeNodeElement_t *m_pElemt;
struct BTreeNode_t_ *m_pLeft;
struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;
2、求二叉树第K层的节点数
（1）递归方式：
给定根节点pRoot：
如果pRoot为空，或者层数KthLevel <= 0，则为空树或者不合要求，则返回0；
如果pRoot不为空，且此时层数KthLevel==1，则此时pRoot为第K层节点之一，则返回1；
如果pRoot不为空，且此时层数KthLevel > 1，则此时需要求pRoot左子树（KthLevel - 1 ）层节点数和pRoot右子树（KthLevel-1）层节点数；
int GetBTreeKthLevelNodesTotal( BTreeNode_t *pRoot, int KthLevel){
if( pRoot == NULL || KthLevel <= 0 )
return 0;
if( pRoot != NULL && KthLevel == 1 )
return 1;
return (GetBTreeKthLevelNodesTotal( pRoot->m_pLeft, KthLevel-1) + GetBTreeKthLevelNodesTotal( pRoot->m_pRight, KthLevel - 1 ) );
}
（2）非递归方式
借助队列实现：
int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
if( pRoot == NULL )
return 0;
queue <BTreeNode_t *> que;
que.push( pRoot );
int curLevelNodesTotal = 0;
int curLevel = 0;
while( !que.empty() ){
++curLevel;//当前层数
curLevelNodesTotal = que.size();
if( curLevel == KthLevel )//如果层数等于给定层数
break;
int cntNode = 0;
while( cntNode < curLevelNodesTotal){//将下一层节点入队
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft != NULL )
que.push(pRoot->m_pLeft);
if( pRoot->m_pRight != NULL )
que.push( pRoot->m_pRight);
}
}
while ( !que.empty() )
que.pop();
if( curLevel == KthLevel )
return curLevelNodesTotal;
return 0; //如果KthLevel大于树的深度
}
3、求二叉树第K层叶子节点数
（1）递归方式
给定节点pRoot：
如果pRoot为空，或者层数KthLevel <= 0, 则为空树或者是层数非法，则返回0；
如果pRoot不为空，且此时层数KthLevel==1时，需要判断是否为叶子节点：
如果pRoot左右子树均为空，则pRoot为第K层叶子节点之一，则返回1；
如果pRoot左右子树之一存在，则pRoot不是叶子节点，则返回0；
如果pRoot不为空，且此时层数KthLevel > 1，需要返回 KthLevel-1层的左子树和右子树结点数。
int GetBTreeKthLevelLeafNodesTotal( BTreeNode_t *pRoot, int KthLevel){
if( pRoot == NULL || KthLevel <= 0 )
return 0;
if( pRoot != NULL && KthLevel == 1 ){
if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )
return 1;
else
return 0;
}
return ( GetBTreeKthLevelLeafNodesTotal( pRoot->m_pLeft, KthLevel - 1) + GetBTreeKthLevelLeafNodesTotal( pRoot->m_pRight, KthLevel -1) );
}
（2）非递归方式
借助队列实现
int GetKthLevelNodesTotal( BTreeNode_t *pRoot, unsigned int KthLevel ){
if( pRoot == NULL )
return 0;
queue <BTreeNode_t *> que;
que.push( pRoot );
int curLevelNodesTotal = 0;
int curLevel = 0;
while( !que.empty() ){
++curLevel;//当前层数
curLevelNodesTotal = que.size();
if( curLevel == KthLevel )//如果层数等于给定层数
break;
int cntNode = 0;
while( cntNode < curLevelNodesTotal){//将下一层节点入队
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft != NULL )
que.push(pRoot->m_pLeft);
if( pRoot->m_pRight != NULL )
que.push( pRoot->m_pRight);
}
}
if( curLevel == KthLevel ){
int cntNode = 0;
int leafNodes = 0;
while( cntNode < curLevelNodesTotal ){
++cntNode;
pRoot = que.front();
que.pop();
if( pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )
leafNodes++;
}
return leafNodes; //返回叶子节点数
}
return 0; //如果KthLevel大于树的深度
}