链接
平衡二叉树的性质为: 要么是一棵空树,要么任何一个节点的左右子树高度差的绝对值不超过 1。给定一棵二叉树,判断这棵二叉树是否为平衡二叉树。
一颗树的高度指的是树的根节点到所有节点的距离中的最大值。
import java.util.Scanner;
public class Main {
private static Info solve(Node root) {
if (root == null) {
return new Info(0, true);
}
Info left = solve(root.left);
Info right = solve(root.right);
int deep = Math.max(left.deep, right.deep) + 1;
boolean isBalance = left.isBalance && right.isBalance && Math.abs(left.deep - right.deep) <= 1;
return new Info(deep, isBalance);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
Node[] nodes = new Node[n + 1];
for (int i = 1; i <= n; ++i) {
nodes[i] = new Node(i);
}
Node root = nodes[in.nextInt()];
for (int i = 1; i <= n; ++i) {
int fa = in.nextInt();
nodes[fa].left = nodes[in.nextInt()];
nodes[fa].right = nodes[in.nextInt()];
}
Info ret = solve(root);
System.out.println(ret.isBalance);
}
}
}
class Info {
int deep;
boolean isBalance;
public Info(int deep, boolean isBalance) {
this.deep = deep;
this.isBalance = isBalance;
}
}
class Node {
Node left;
Node right;
int val;
public Node(int val) {
this.val = val;
}
}