二叉树叶节点总数的递归算法
计算叶节点总数的算法与关于打印叶节点的问题非常相似。 以下是要遵循的实际步骤：
1）如果节点为空返回0，这也是我们递归算法的基本情况
2）如果遇到叶节点，则返回1
3）左、右子树重复该过程。
4）返回左、右子树叶节点的和
下面是基于上述逻辑的示例代码
private int countLeaves(TreeNode node) {
if (node == null)
return 0;
if (node.isLeaf()) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}
|
也许您注意到这个方法是私有的，我已经在BinaryTree类中声明了这个方法。为了在外部访问它，我创建了另一个方法countLeafNodesRecursivel（），如下所示：
public int countLeafNodesRecursively() {
return countLeaves(root);
}
|
这样做有两个原因，最初的方法需要一个起始节点，它应该是root。 客户端只需调用此方法就可以了，因为Bin已经可以使用BinaryTree类。 然后，包装方法将根传递给计算叶节点的实际方法。 包装方法是公共的，这样客户端就可以访问它，而实际的方法是私有的，这样任何人都无法看到它，开发人员将来可以在不影响客户端的情况下更改实现。这实际上是揭示需要参数的递归方法的标准模式。
二叉树叶节点总数的迭代算法
叶节点计数的递归算法非常简单，迭代算法也非常简单。类似于迭代的InOrder遍历示例，我们使用了一个堆栈来遍历二叉树。下面是迭代算法获得二叉树叶节点总数的步骤：
1）如果根为空，则返回零。
2）以零开始计数
3）将根推入堆栈
4）循环直到堆栈不为空
5）弹出最后一个节点，推送最后一个节点的左右子节点(如果它们不为空)。
6）增加计数
在循环结束时，计数包含叶节点的总数。下面是基于上述逻辑和算法的示例代码：
public int countLeafNodes() {
if (root == null) {
return 0;
}
Stack stack = new Stack<>();
stack.push(root);
int count = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null)
stack.push(node.left);
if (node.right != null)
stack.push(node.right);
if (node.isLeaf())
count++;
}
return count;
}
}
|
你可以看到逻辑非常简单。这个算法的时间复杂度是O（N），因为您需要访问二叉树的所有节点来计算叶节点的总数。堆栈是一个后进先出的数据结构，我们使用了jdk实现java.util.stack，它还扩展了vector类。
用Java程序计算二叉树中叶节点的数量
这是用Java计算给定二叉树中叶节点总数的完整程序。 该程序演示了递归和迭代算法来解决这个问题。在此程序中，我们将使用以下二叉树进行测试。
a
/ \
b f
/ \ / \
c e g h
/ \
d k
由于此树中有四个叶节点（D、E、G和K），所以您的程序应该打印4个。CountLeafNodesRecursive（）方法使用递归解决此问题，CountLeafNodes（）不使用递归解决此问题。两种方法前面已作阐述。
import java.util.Stack;
/*
* Java Program to count all leaf nodes of binary tree
* with and without recursion.
* input : a
* / \
* b f
* / \ / \
* c e g h
* / \
* d k
*
* output: 4
*/
public class Main {
public static void main(String args) throws Exception {
// let's create a binary tree
BinaryTree bt = new BinaryTree();
bt.root = new BinaryTree.TreeNode("a");
bt.root.left = new BinaryTree.TreeNode("b");
bt.root.right = new BinaryTree.TreeNode("f");
bt.root.left.left = new BinaryTree.TreeNode("c");
bt.root.left.right = new BinaryTree.TreeNode("e");
bt.root.left.left.left = new BinaryTree.TreeNode("d");
bt.root.right.left = new BinaryTree.TreeNode("g");
bt.root.right.right = new BinaryTree.TreeNode("h");
bt.root.right.right.right = new BinaryTree.TreeNode("k");
// count all leaf nodes of binary tree using recursion
System.out
.println("total number of leaf nodes of binary tree in Java (recursively)");
System.out.println(bt.countLeafNodesRecursively());
// count all leaf nodes of binary tree without recursion
System.out
.println("count of leaf nodes of binary tree in Java (iteration)");
System.out.println(bt.countLeafNodes());
}
}
class BinaryTree {
static class TreeNode {
String value;
TreeNode left, right;
TreeNode(String value) {
this.value = value;
left = right = null;
}
boolean isLeaf() {
return left == null ? right == null : false;
}
}
// root of binary tree
TreeNode root;
/**
* Java method to calculate number of leaf node in binary tree.
*
* @param node
* @return count of leaf nodes.
*/
public int countLeafNodesRecursively() {
return countLeaves(root);
}
private int countLeaves(TreeNode node) {
if (node == null)
return 0;
if (node.isLeaf()) {
return 1;
} else {
return countLeaves(node.left) + countLeaves(node.right);
}
}
/**
* Java method to count leaf nodes using iteration
*
* @param root
* @return number of leaf nodes
*
*/
public int countLeafNodes() {
if (root == null) {
return 0;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
int count = 0;
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
if (node.left != null)
stack.push(node.left);
if (node.right != null)
stack.push(node.right);
if (node.isLeaf())
count++;
}
return count;
}
}
Output
total number of leaf nodes of a binary tree in Java (recursively)
4
count of leaf nodes of a binary tree in Java (iteration)
4
|
这就是如何用Java计算二叉树中叶节点的数量。