用java算法实现: 求解一棵二叉树的结点个数和深度。
时间: 2024-11-06 12:17:09 浏览: 13
编写一个将二叉树中每个结点的左右孩子交换的算法。
在 Java 中,求解一棵二叉树的节点个数(也称为大小)和深度可以通过递归的方式实现。以下是两个分别计算节点个数(`countNodes`)和深度(`calculateDepth`)的函数:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
// Constructor for the tree node
TreeNode(int val) {
this.val = val;
this.left = null;
this.right = null;
}
}
public class BinaryTreeUtils {
public static int countNodes(TreeNode root) {
if (root == null) {
return 0; // 如果根节点为空,返回0表示空树
} else {
return 1 + countNodes(root.left) + countNodes(root.right); // 递归地计算左右子树的节点数并加一
}
}
public static int calculateDepth(TreeNode root) {
if (root == null) {
return 0; // 空树的深度为0
} else {
int leftDepth = calculateDepth(root.left);
int rightDepth = calculateDepth(root.right);
// 返回左、右子树的最大深度加1,再加上当前节点
return Math.max(leftDepth, rightDepth) + 1;
}
}
}
```
使用这两个函数时,先创建一个 `TreeNode` 对象表示二叉树的根节点,然后调用 `countNodes(root)` 来获取节点总数,调用 `calculateDepth(root)` 来获取树的深度。
阅读全文