1. /**
    2.  * 给定一棵树的头节点，判断这棵树是否为平衡二叉树
    3.  * 平衡二叉树定义：
    4.  * 每一颗子数左右子树的高高度差不能超过1
    5.  */
    6. public class Code03_IsBalanced {
    8.     public static class Node {
    9.         public int value;
    10.         public Node left;
    11.         public Node right;
    13.         public Node(int data) {
    14.             this.value = data;
    15.         }
    16.     }
    18.     public static boolean isBalanced1(Node head) {
    19.         boolean[] ans = new boolean[1];
    20.         ans[0] = true;
    21.         process1(head, ans);
    22.         return ans[0];
    23.     }
    25.     public static int process1(Node head, boolean[] ans) {
    26.         if (!ans[0] || head == null) {
    27.             return -1;
    28.         }
    29.         int leftHeight = process1(head.left, ans);
    30.         int rightHeight = process1(head.right, ans);
    31.         if (Math.abs(leftHeight - rightHeight) > 1) {
    32.             ans[0] = false;
    33.         }
    34.         return Math.max(leftHeight, rightHeight) + 1;
    35.     }
    37.     /**
    38.      * 主函数
    39.      * @param head
    40.      * @return
    41.      */
    42.     public static boolean isBalanced2(Node head) {
    43.         return process(head).isBalanced;
    44.     }
    46.     /**
    47.      * 信息体类
    48.      */
    49.     public static class Info {
    50.         public boolean isBalanced;
    51.         public int height;
    53.         public Info(boolean i, int h) {
    54.             isBalanced = i;
    55.             height = h;
    56.         }
    57.     }
    59.     /**
    60.      * 递归过程
    61.      * @param x
    62.      */
    63.     public static Info process(Node x) {
    65.         if (x == null) {
    66.             return new Info(true, 0);
    67.         }
    69.         Info leftInfo = process(x.left);
    70.         Info rightInfo = process(x.right);
    71.         // 树的高度
    72.         int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    73.         // 先认为自己是平衡的，然后看下面条件是否违反。
    74.         boolean isBalanced = true;
    75.         if (!leftInfo.isBalanced) {  // 如果左树不平，不平
    76.             isBalanced = false;
    77.         }
    78.         if (!rightInfo.isBalanced) {  // 如果右树不平，不平
    79.             isBalanced = false;
    80.         }
    81.         if (Math.abs(leftInfo.height - rightInfo.height) > 1) {  // 左右两侧树的高度差》1 不平
    82.             isBalanced = false;
    83.         }
    84.         return new Info(isBalanced, height);
    85.     }
    88.     // for test
    89.     public static Node generateRandomBST(int maxLevel, int maxValue) {
    90.         return generate(1, maxLevel, maxValue);
    91.     }
    93.     // for test
    94.     public static Node generate(int level, int maxLevel, int maxValue) {
    95.         if (level > maxLevel || Math.random() < 0.5) {
    96.             return null;
    97.         }
    98.         Node head = new Node((int) (Math.random() * maxValue));
    99.         head.left = generate(level + 1, maxLevel, maxValue);
    100.         head.right = generate(level + 1, maxLevel, maxValue);
    101.         return head;
    102.     }
    104.     public static void main(String[] args) {
    105.         int maxLevel = 5;
    106.         int maxValue = 100;
    107.         int testTimes = 1000000;
    108.         for (int i = 0; i < testTimes; i++) {
    109.             Node head = generateRandomBST(maxLevel, maxValue);
    110.             if (isBalanced1(head) != isBalanced2(head)) {
    111.                 System.out.println("Oops!");
    112.             }
    113.         }
    114.         System.out.println("finish!");
    115.     }
    117. }