请写出一段根据叶子节点数计算完全二叉树所有节点数的java代码
时间: 2023-05-31 17:06:10 浏览: 111
public static int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (leftHeight == rightHeight) { // 左子树和右子树高度相等,说明左子树是一棵满二叉树
int leftNodes = (int) Math.pow(2, leftHeight) - 1; // 左子树的节点数
return leftNodes + countNodes(root.right) + 1; // 加上右子树的节点数和根节点
} else { // 左子树和右子树高度不相等,说明右子树是一棵满二叉树
int rightNodes = (int) Math.pow(2, rightHeight) - 1; // 右子树的节点数
return rightNodes + countNodes(root.left) + 1; // 加上左子树的节点数和根节点
}
}
// 获取以root为根节点的二叉树的高度
private static int getHeight(TreeNode root) {
if (root == null) {
return 0;
}
return getHeight(root.left) + 1; // 因为是完全二叉树,所以只需要计算左子树的高度
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
阅读全文