用递归的算法求取二叉树每层节点个JAVA语言
时间: 2023-05-28 12:07:57 浏览: 65
以下是使用递归算法求取二叉树每层节点个数的Java代码实现:
```java
public class BinaryTreeLevelCount {
// 计算每层节点个数的方法
public static void countNodesByLevel(TreeNode root, int level, int[] counts) {
if (root == null) {
return;
}
// 如果当前层数为level,则将节点数+1
if (level == 1) {
counts[0]++;
} else if (level > 1) {
// 否则递归计算左右子树的节点数
countNodesByLevel(root.left, level-1, counts);
countNodesByLevel(root.right, level-1, counts);
}
}
// 获取二叉树的深度
public static int getDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = getDepth(root.left);
int rightDepth = getDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
// 计算二叉树每层节点数的方法
public static int[] countNodesByLevel(TreeNode root) {
int depth = getDepth(root); // 获取二叉树深度
int[] counts = new int[depth]; // 初始化每层节点数数组
for (int i = 1; i <= depth; i++) { // 逐层计算节点数
countNodesByLevel(root, i, counts);
}
return counts;
}
}
```
其中,`countNodesByLevel`方法是递归计算每层节点数的核心方法,它传入当前节点、当前层数和每层节点数数组,如果当前层数为1,则将该层节点数+1;否则递归计算左右子树的节点数。`getDepth`方法用于获取二叉树的深度,`countNodesByLevel`方法则是计算每层节点数的入口方法,它先获取二叉树的深度,然后逐层计算每层节点数,最终返回每层节点数数组。