六：二叉樹中第k層節點個數與二叉樹葉子節點個數

二叉樹中第k層節點個數

遞歸解法：

（1）如果二叉樹為空或者k<1傳回0

（2）如果二叉樹不為空并且k==1，傳回1

（3）如果二叉樹不為空且k>1，傳回左子樹中k-1層的節點個數與右子樹k-1層節點個數之和

代碼如下：

int GetNodeNumKthLevel(BinaryTreeNode *pRoot, int k) 

{ 

   if(pRoot == NULL || k < 1) 

       return 0; 

   if(k == 1) 

       return 1; 

   int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子樹中k-1層的節點個數 

   int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子樹中k-1層的節點個數 

   return (numLeft + numRight); 

}

二叉樹葉子節點個數

遞歸方式

（1）如果給定節點pRoot為NULL，則是空樹，葉子節點為0，傳回0；

（2）如果給定節點pRoot左右子樹均為NULL，則是葉子節點，且葉子節點數為1，傳回1；

（3）如果給定節點pRoot左右子樹不都為NULL，則不是葉子節點，以pRoot為根節點的子樹葉子節點數=pRoot左子樹葉子節點數+pRoot右子樹葉子節點數

代碼如下

int  GetLeafNum(BinaryTreeNode *pRoot)

{

    if( pRoot ==NULL )

        return0;

    if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL )

        return1;

    return (GetLeafNum( pRoot->m_pLeft) + GetLeafNum ( pRoot->m_pRight) );

}

非遞歸方式：

用非遞歸便利的方式周遊二叉樹，便利的同時，判斷目前節點是否為葉子節點，如果是，計數器計數。