Question

假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊

Answer 1

• 叶子节点：没有孩子节点的节点

下面我给出两种求解思路，其中就包括你要的递归求解。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<Integer> 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<Integer> root){
		int count = 0; //叶子节点总数
		LinkQueue<BinaryTreeNode<Integer>> queue = new LinkQueue<>();
		if(root != null){
			queue.enQueue(root);
		}
		
		while (!queue.isEmpty()) {
			BinaryTreeNode<Integer> 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<BinaryTreeNode<Integer>> queue = new LinkQueue<BinaryTreeNode<Integer>>();
		BinaryTreeNode<Integer> root = new BinaryTreeNode<>(1); //根节点
		
		queue.enQueue(root);
		BinaryTreeNode<Integer> temp = null;
		for(int i=2;i<10;i=i+2){
			BinaryTreeNode<Integer> tmpNode1 = new BinaryTreeNode<>(i);
			BinaryTreeNode<Integer> 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 <K>
 */
public class BinaryTreeNode<K extends Object> {
	private K data; // 数据
	private BinaryTreeNode<K> left; //左孩子节点
	private BinaryTreeNode<K> right; //右孩子节点
	
	public BinaryTreeNode(K data) {
		this.data = data;
	}

	public BinaryTreeNode(K data, BinaryTreeNode<K> left, BinaryTreeNode<K> 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<K> getLeft() {
		return left;
	}

	public void setLeft(BinaryTreeNode<K> left) {
		this.left = left;
	}

	public BinaryTreeNode<K> getRight() {
		return right;
	}

	public void setRight(BinaryTreeNode<K> right) {
		this.right = right;
	}

}

ii）LinkQueue.java：

package cn.zifangsky.queue;

import cn.zifangsky.linkedlist.SinglyNode;

/**
 * 基于单链表实现的队列
 * @author zifangsky
 * @param <K>
 */
public class LinkQueue<K extends Object> implements Queue<K>{
	private SinglyNode<K> frontNode; //队首节点
	private SinglyNode<K> 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<K> currentNode = frontNode;
		while (currentNode != null) {
			length++;
			currentNode = currentNode.getNext();
		}
		
		return length;
	}
	
	/**
	 * 入队：在链表表尾插入数据
	 * @时间复杂度 O(1)
	 * @param data
	 */
	@Override
	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
	 */
	@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<K> 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 <K>
 */
public class SinglyNode<K extends Object> {
	private K data; // 数据
	private SinglyNode<K> next; // 该节点的下个节点

	public SinglyNode(K data) {
		this.data = data;
	}

	public SinglyNode(K data, SinglyNode<K> next) {
		this.data = data;
		this.next = next;
	}

	public K getData() {
		return data;
	}

	public void setData(K data) {
		this.data = data;
	}

	public SinglyNode<K> getNext() {
		return next;
	}

	public void setNext(SinglyNode<K> next) {
		this.next = next;
	}

	@Override
	public String toString() {
		return "SinglyNode [data=" + data + "]";
	}

}