二叉树是否为平衡二叉树

链接
平衡二叉树的性质为: 要么是一棵空树,要么任何一个节点的左右子树高度差的绝对值不超过 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;
    }
}
上一篇:element ui el-table中默认的排序三角形改变样式


下一篇:vue el-input输入框el-autocomplete下拉列表样式修改