给定一个二又树,要求舅写一个Java程序,判断二叉树是否为平衡二又树单入格式:单入个整数,每三个数为一组,分别用x、y、表示。其中x为节点,y、Z表示节点x的左右子树,如果y或z为0,则表示没有对应的左子树或右子树。给出格式,true或者false。用java语言实现
时间: 2024-02-15 09:04:32 浏览: 66
好的,我可以帮您解答这个问题。下面是Java程序的实现:
```java
import java.util.*;
public class BalancedBinaryTree {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) {
this.val = val;
left = right = null;
}
}
public static boolean isBalanced(TreeNode root) {
if (root == null) return true;
int leftHeight = getHeight(root.left);
int rightHeight = getHeight(root.right);
if (Math.abs(leftHeight - rightHeight) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
private static int getHeight(TreeNode node) {
if (node == null) return 0;
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
String[] nodes = input.trim().split(",");
Map<Integer, TreeNode> map = new HashMap<>();
for (String node : nodes) {
String[] nums = node.trim().split("\\s+");
int val = Integer.parseInt(nums[0]);
TreeNode cur = map.getOrDefault(val, new TreeNode(val));
if (nums.length >= 2 && Integer.parseInt(nums[1]) != 0) {
int leftVal = Integer.parseInt(nums[1]);
TreeNode left = map.getOrDefault(leftVal, new TreeNode(leftVal));
cur.left = left;
map.put(leftVal, left);
}
if (nums.length == 3 && Integer.parseInt(nums[2]) != 0) {
int rightVal = Integer.parseInt(nums[2]);
TreeNode right = map.getOrDefault(rightVal, new TreeNode(rightVal));
cur.right = right;
map.put(rightVal, right);
}
map.put(val, cur);
}
System.out.println(isBalanced(map.get(1)));
}
}
```
该程序实现了以下功能:
1. 定义了一个 `TreeNode` 类,表示二叉树节点。
2. 实现了一个 `isBalanced` 方法,判断给定的二叉树是否为平衡二叉树。
3. 实现了一个 `getHeight` 方法,用于计算二叉树节点的高度。
4. 在 `main` 方法中,从用户输入中读取二叉树节点信息,构建二叉树,并判断该二叉树是否为平衡二叉树。
具体实现流程如下:
1. 从标准输入中读取一行字符串,表示二叉树的节点信息。
2. 将字符串按逗号分隔,得到每个节点的信息。
3. 遍历每个节点,根据节点信息构建二叉树。
4. 调用 `isBalanced` 方法判断二叉树是否为平衡二叉树。
5. 将判断结果输出到标准输出中。
希望这个程序能够帮助您解决问题。
阅读全文