用详细的java算法实现: 求解一棵二叉树的结点个数和深度。
时间: 2024-11-06 12:17:40 浏览: 10
编写一个将二叉树中每个结点的左右孩子交换的算法。
在Java中,我们可以使用递归的方式来求解一棵二叉树的节点总数(即树的大小)和最大深度。以下是详细的算法实现:
```java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public class BinaryTreeUtils {
public static int countNodes(TreeNode root) {
// 如果根节点为空,返回0
if (root == null) return 0;
// 否则,递归计算左子树和右子树的节点数,并加上当前节点
return 1 + countNodes(root.left) + countNodes(root.right);
}
public static int maxDepth(TreeNode root) {
// 递归终止条件:如果根节点为空,深度为0
if (root == null) return 0;
// 计算左子树的最大深度和右子树的最大深度,取较大者加1作为当前层的深度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
// 返回当前层的深度
return Math.max(leftDepth, rightDepth) + 1;
}
}
```
在这个代码中,`countNodes`函数用于计算树的节点总数,而`maxDepth`函数则是用来找出树的最大深度。注意这两个方法都是通过递归遍历每个节点并计算其子树来实现的。
阅读全文