葉子節點：沒有孩子節點的節點
也就是說，當我們明白了葉子節點的定義後，只需要遍歷壹遍二叉樹，把符合這種條件（左孩子節點和右孩子節點都為NULL的節點）的節點統計出來就可以了。
於是，實際上這個問題也就轉化成了如何遍歷二叉樹？很顯然，遍歷二叉樹是可以有多種方式的，如：前序遍歷（遞歸/非遞歸）、中序遍歷（遞歸/非遞歸）、後序遍歷（遞歸/非遞歸）、層次遍歷等等。
下面我將給出使用遞歸前序遍歷以及層次遍歷兩種思路實現的求解葉子節點的示例代碼吧，僅供參考。其他幾種實現方式思路類似，可自行嘗試。示例代碼如下：
package?cn.zifangsky.tree.questions;import?org.junit.Test;
import?cn.zifangsky.queue.LinkQueue;
import?cn.zifangsky.tree.BinaryTreeNode;
/**
*?求二叉樹中葉子節點的個數 *?@author?Administrator * */public?class?Question2?{
/**
?*?通過遞歸前序遍歷獲取葉子節點個數
?*?@param?root
?*?@return
?*/
public?int?getNumberOfLeavesByPreOrder(BinaryTreeNode?root){
if(root?==?null){
return?0;
}else{
if(root.getLeft()?==?null?&&?root.getRight()?==?null){?//葉子節點
return?1;
}else{
return?getNumberOfLeavesByPreOrder(root.getLeft())?+?getNumberOfLeavesByPreOrder(root.getRight());
}
}
}
/**
?*?使用層次遍歷獲取二叉樹葉子節點個數
?*?
?*?@時間復雜度?O(n)
?*?@param?root
?*/
public?int?getNumberOfLeavesByQueue(BinaryTreeNode?root){
int?count?=?0;?//葉子節點總數
LinkQueue<BinaryTreeNode>?queue?=?new?LinkQueue<>();
if(root?!=?null){
queue.enQueue(root);
}
while?(!queue.isEmpty())?{
BinaryTreeNode?temp?=?(BinaryTreeNode)?queue.deQueue();
//葉子節點：左孩子節點和右孩子節點都為NULL的節點
if(temp.getLeft()?==?null?&&?temp.getRight()?==?null){
count++;
}else{
if(temp.getLeft()?!=?null){
queue.enQueue(temp.getLeft());
}
if(temp.getRight()?!=?null){
queue.enQueue(temp.getRight());
}
}
}
return?count;
}
/**
?*?測試用例
?*/
@Test
public?void?testMethods(){
/**
?*?使用隊列構造壹個供測試使用的二叉樹
?*?1
?*23
?*?4?5?6?7
?*8?9?
?*/
LinkQueue<BinaryTreeNode>?queue?=?new?LinkQueue<BinaryTreeNode>();
BinaryTreeNode?root?=?new?BinaryTreeNode(1);?//根節點
queue.enQueue(root);
BinaryTreeNode?temp?=?null;
for(int?i=2;i<10;i=i+2){
BinaryTreeNode?tmpNode1?=?new?BinaryTreeNode(i);
BinaryTreeNode?tmpNode2?=?new?BinaryTreeNode(i+1);
temp?=?(BinaryTreeNode)?queue.deQueue();
temp.setLeft(tmpNode1);
temp.setRight(tmpNode2);
if(i?!=?4)
queue.enQueue(tmpNode1);
queue.enQueue(tmpNode2);
}
System.out.println("葉子節點個數是："?+?getNumberOfLeavesByPreOrder(root));
System.out.println("葉子節點個數是："?+?getNumberOfLeavesByQueue(root));
}
}
測試代碼輸出如下：
葉子節點個數是：5葉子節點個數是：5
附：
二叉樹節點BinaryTreeNode的定義：
package?cn.zifangsky.tree;public?class?BinaryTreeNode?{
private?int?data;?//?數據
private?BinaryTreeNode?left;?//左孩子節點
private?BinaryTreeNode?right;?//右孩子節點
public?BinaryTreeNode(int?data)?{
this.data?=?data;
}
public?BinaryTreeNode(int?data,?BinaryTreeNode?left,?BinaryTreeNode?right)?{
this.data?=?data;
this.left?=?left;
this.right?=?right;
}
public?int?getData()?{
return?data;
}
public?void?setData(int?data)?{
this.data?=?data;
}
public?BinaryTreeNode?getLeft()?{
return?left;
}
public?void?setLeft(BinaryTreeNode?left)?{
this.left?=?left;
}
public?BinaryTreeNode?getRight()?{
return?right;
}
public?void?setRight(BinaryTreeNode?right)?{
this.right?=?right;
}
}
隊列LinkQueue的定義：
package?cn.zifangsky.queue;import?cn.zifangsky.linkedlist.SinglyNode;
/**
*?基於單鏈表實現的隊列 *?@author?zifangsky *?@param?<K> */public?class?LinkQueue<K?extends?Object>{
private?SinglyNode<?>?frontNode;?//隊首節點
private?SinglyNode<?>?rearNode;?//隊尾節點
public?LinkQueue()?{
frontNode?=?null;
rearNode?=?null;
}
/**
?*?返回隊列是否為空
?*?@時間復雜度?O(1)
?*?@return
?*/
public?boolean?isEmpty(){
return?(frontNode?==?null);
}
/**
?*?返回存儲在隊列的元素個數
?*?@時間復雜度?O(n)
?*?@return
?*/
public?int?size(){
int?length?=?0;
SinglyNode<?>?currentNode?=?frontNode;
while?(currentNode?!=?null)?{
length++;
currentNode?=?currentNode.getNext();
}
return?length;
}
/**
?*?入隊：在鏈表表尾插入數據
?*?@時間復雜度?O(1)
?*?@param?data
?*/
public?void?enQueue(K?data){
SinglyNode<K>?newNode?=?new?SinglyNode<K>(data);
if(rearNode?!=?null){
rearNode.setNext(newNode);
}
rearNode?=?newNode;
if(frontNode?==?null){
frontNode?=?rearNode;
}
}
/**
?*?出隊：刪除表頭節點
?*?@時間復雜度?O(1)
?*?@return
?*/
public?Object?deQueue(){
if(isEmpty()){
throw?new?RuntimeException("Queue?Empty!");
}else{
Object?result?=?frontNode.getData();
if(frontNode?==?rearNode){
frontNode?=?null;
rearNode?=?null;
}else{
frontNode?=?frontNode.getNext();
}
return?result;
}
}
}
單鏈表節點SinglyNode的定義：
package?cn.zifangsky.linkedlist;/**
*?單鏈表的定義 *?@author?zifangsky *?@param?<K> */public?class?SinglyNode<K?extends?Object>?{
private?K?data;?//?數據
private?SinglyNode<?>?next;?//?該節點的下個節點
public?SinglyNode(K?data)?{
this.data?=?data;
}
public?SinglyNode(K?data,?SinglyNode<?>?next)?{
this.data?=?data;
this.next?=?next;
}
public?K?getData()?{
return?data;
}
public?void?setData(K?data)?{
this.data?=?data;
}
public?SinglyNode<?>?getNext()?{
return?next;
}
public?void?setNext(SinglyNode<?>?next)?{
this.next?=?next;
}
@Override
public?String?toString()?{
return?"SinglyNode?[data="?+?data?+?"]";
}
}