1. /**
    2.  * 满二叉树
    3.  * 高度为h的满二叉树的节点数为 2^h - 1
    4.  */
    5. public class Code04_IsFull {
    7.     public static class Node {
    8.         public int value;
    9.         public Node left;
    10.         public Node right;
    12.         public Node(int data) {
    13.             this.value = data;
    14.         }
    15.     }
    17.     public static boolean isFull1(Node head) {
    18.         if (head == null) {
    19.             return true;
    20.         }
    21.         int height = h(head);
    22.         int nodes = n(head);
    23.         return (1 << height) - 1 == nodes;
    24.     }
    26.     public static int h(Node head) {
    27.         if (head == null) {
    28.             return 0;
    29.         }
    30.         return Math.max(h(head.left), h(head.right)) + 1;
    31.     }
    33.     public static int n(Node head) {
    34.         if (head == null) {
    35.             return 0;
    36.         }
    37.         return n(head.left) + n(head.right) + 1;
    38.     }
    40.     public static boolean isFull2(Node head) {
    41.         if (head == null) {
    42.             return true;
    43.         }
    44.         Info all = process(head);
    45.         return (1 << all.height) - 1 == all.nodes;
    46.     }
    48.     public static class Info {
    49.         public int height;
    50.         public int nodes;
    52.         public Info(int h, int n) {
    53.             height = h;
    54.             nodes = n;
    55.         }
    56.     }
    58.     public static Info process(Node head) {
    59.         if (head == null) {
    60.             return new Info(0, 0);
    61.         }
    62.         Info leftInfo = process(head.left);
    63.         Info rightInfo = process(head.right);
    64.         int height = Math.max(leftInfo.height, rightInfo.height) + 1;
    65.         int nodes = leftInfo.nodes + rightInfo.nodes + 1;
    66.         return new Info(height, nodes);
    67.     }
    69.     // for test
    70.     public static Node generateRandomBST(int maxLevel, int maxValue) {
    71.         return generate(1, maxLevel, maxValue);
    72.     }
    74.     // for test
    75.     public static Node generate(int level, int maxLevel, int maxValue) {
    76.         if (level > maxLevel || Math.random() < 0.5) {
    77.             return null;
    78.         }
    79.         Node head = new Node((int) (Math.random() * maxValue));
    80.         head.left = generate(level + 1, maxLevel, maxValue);
    81.         head.right = generate(level + 1, maxLevel, maxValue);
    82.         return head;
    83.     }
    85.     public static void main(String[] args) {
    86.         int maxLevel = 5;
    87.         int maxValue = 100;
    88.         int testTimes = 1000000;
    89.         for (int i = 0; i < testTimes; i++) {
    90.             Node head = generateRandomBST(maxLevel, maxValue);
    91.             if (isFull1(head) != isFull2(head)) {
    92.                 System.out.println("Oops!");
    93.             }
    94.         }
    95.         System.out.println("finish!");
    96.     }
    98. }