110. 平衡二叉树_pycharm构建平衡二叉树

题目：

110. 平衡二叉树
面试题55 - II. 平衡二叉树

题解：

1. 解释一：

2. 解释二：

3. 注意点：

代码：

/**
 * code110
 */

public class code110 {

    public static boolean isBalanced(TreeNode root) {
        // 它是一棵空树
        if (root == null) {
            return true;
        }
        // 它的左右两个子树的高度差的绝对值不超过1
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
            return false;
        }
        // 左右两个子树都是一棵平衡二叉树
        if (!isBalanced(root.left)) {
            return false;
        }
        if (!isBalanced(root.right)) {
            return false;
        }
        return true;
    }

    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    public static void main(String[] args) {
        Integer nums1[] = { 3, 9, 20, null, null, 15, 7 };
        TreeNode tree1 = ConstructTree.constructTree(nums1);
        System.out.println("***************************************");
        TreeOperation.show(tree1);
        boolean flag1 = isBalanced(tree1);
        System.out.println(flag1);
        System.out.println("***************************************");

        Integer nums2[] = { 1, 2, 2, 3, 3, null, null, 4, 4 };
        TreeNode tree2 = ConstructTree.constructTree(nums2);
        TreeOperation.show(tree2);
        boolean flag2 = isBalanced(tree2);
        System.out.println(flag2);
        System.out.println("***************************************");

        Integer nums3[] = { 1, 2, 2, 3, null, null, 3, 4, null, null, 4 };
        TreeNode tree3 = ConstructTree.constructTree(nums3);
        TreeOperation.show(tree3);
        boolean flag3 = isBalanced(tree3);
        System.out.println(flag3);
        System.out.println("***************************************");

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

参考：

1. 平衡二叉树
2. 110. 平衡二叉树（从底至顶，从顶至底）
3. 自顶向下和自底向上
4. 平衡二叉树
5. java递归求解
6. 详细通俗的思路分析，多解法
7. 三道题套路解决递归问题
8. 面试题55 - II. 平衡二叉树（从底至顶、从顶至底，清晰图解）