下面我给出两种求解思路，其中就包括你要的递归求解。Java版的示例代码如下：
package cn.zifangsky.tree.binarytree.questions;
import org.junit.Test;
import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.tree.binarytree.BinaryTreeNode;
/**
* 求二叉树中叶子节点的个数
* @author zifangsky
*
*/
public class Question2 {
/**
* 通过递归遍历获取叶子节点个数
*
* @时间复杂度 O(n)
* @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> queue = new LinkQueue<>();
if(root != null){
queue.enQueue(root);
}
while (!queue.isEmpty()) {
BinaryTreeNode temp = 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
* 2 3
* 4 5 6 7
* 8 9
*/
LinkQueue> queue = new LinkQueue>();
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 = 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
附：上面代码中用到的两个类的定义：
i）BinaryTreeNode.java：
package cn.zifangsky.tree.binarytree;
/**
* 二叉树的单个节点定义
* @author zifangsky
*
* @param
*/
public class BinaryTreeNode {
private K data; // 数据
private BinaryTreeNode left; //左孩子节点
private BinaryTreeNode right; //右孩子节点
public BinaryTreeNode(K data) {
this.data = data;
}
public BinaryTreeNode(K data, BinaryTreeNode left, BinaryTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public K getData() {
return data;
}
public void setData(K 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;
}
}
ii）LinkQueue.java：
package cn.zifangsky.queue;
import cn.zifangsky.linkedlist.SinglyNode;
/**
* 基于单链表实现的队列
* @author zifangsky
* @param
*/
public class LinkQueue implements Queue{
private SinglyNode frontNode; //队首节点
private SinglyNode rearNode; //队尾节点
public LinkQueue() {
frontNode = null;
rearNode = null;
}
/**
* 返回队列是否为空
* @时间复杂度 O(1)
* @return
*/
@Override
public boolean isEmpty(){
return (frontNode == null);
}
/**
* 返回存储在队列的元素个数
* @时间复杂度 O(n)
* @return
*/
@Override
public int size(){
int length = 0;
SinglyNode currentNode = frontNode;
while (currentNode != null) {
length++;
currentNode = currentNode.getNext();
}
return length;
}
/**
* 入队：在链表表尾插入数据
* @时间复杂度 O(1)
* @param data
*/
@Override
public void enQueue(K data){
SinglyNode newNode = new SinglyNode(data);
if(rearNode != null){
rearNode.setNext(newNode);
}
rearNode = newNode;
if(frontNode == null){
frontNode = rearNode;
}
}
/**
* 出队：删除表头节点
* @时间复杂度 O(1)
* @return
*/
@Override
public K deQueue(){
if(isEmpty()){
throw new RuntimeException("Queue Empty!");
}else{
K result = frontNode.getData();
if(frontNode == rearNode){
frontNode = null;
rearNode = null;
}else{
frontNode = frontNode.getNext();
}
return result;
}
}
/**
* 返回队首的元素，但不删除
* @时间复杂度 O(1)
*/
@Override
public K front() {
if(isEmpty()){
throw new RuntimeException("Queue Empty!");
}else{
return frontNode.getData();
}
}
/**
* 遍历队列
* @时间复杂度 O(n)
* @return
*/
@Override
public void print() {
SinglyNode tmpNode = frontNode;
while (tmpNode != null) {
System.out.print(tmpNode.getData() + " ");
tmpNode = tmpNode.getNext();
}
}
/**
* 删除整个队列
* @时间复杂度 O(1)
* @return
*/
@Override
public void deleteQueue() {
frontNode = null;
rearNode = null;
}
}
iii）SinglyNode.java：
package cn.zifangsky.linkedlist;
/**
* 单链表的定义
*
* @author zifangsky
* @param
*/
public class SinglyNode {
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 + "]";
}
}
