1. 题目描述

判断二叉树是不是平衡二叉树

2. 测试案例

树为空
树不空

3. 最佳思路

使用二叉树的递归套路去解题：

4. 代码

public class Main {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    static class Info {
        public boolean isBalance;
        public int height;

        public Info(boolean isBalance, int height) {
            this.isBalance = isBalance;
            this.height = height;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.left.left = new Node(8);
        System.out.println(isBalanceTree(root));
    }

    // 判断此树是否是平衡二叉树
    public static boolean isBalanceTree(Node root) {
        return pos(root).isBalance;
    }

    // 后序遍历的变形
    public static Info pos(Node root) {
        /* 0. 边界条件 */
        if (root == null)
            return new Info(true, 0);
        
        /* 1. 获取左右子树的信息 */
        Info leftInfo = pos(root.left);
        Info rightInfo = pos(root.right);
        
        /* 2. 处理好当前结点的Info信息，并返回 */
        Info info = new Info(false, Math.max(leftInfo.height, rightInfo.height) + 1); // 当前结点要返回的信息
        if (leftInfo.isBalance == true && rightInfo.isBalance == true && Math.abs(leftInfo.height - rightInfo.height) <= 1)
            info.isBalance = true;
        return info;
    }

}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/84582.html