思想上的提醒，极度模板化代码

1、给定一颗二叉树的头结点head，返回这颗二叉树是不是平衡二叉树

平衡二叉树：在一棵二叉树中，每一颗子树左树的最大高度和右数的最大高度相差的绝对值不超过1

  1. public static boolean isCBT1(Node head) {
  2.     if (head == null) {
  3.         return true;
  4.     }
  5.     LinkedList<Node> queue = new LinkedList<>();
  6.     // 是否遇到过左右两个孩子不双全的节点
  7.     boolean leaf = false;
  8.     Node l = null;
  9.     Node r = null;
  10.     queue.add(head);
  11.     while (!queue.isEmpty()) {
  12.         head = queue.poll();
  13.         l = head.left;
  14.         r = head.right;
  15.         if (
  16.             // 如果遇到了不双全的节点之后，又发现当前节点不是叶节点
  17.             (leaf && (l != null || r != null)) 
  18.             || 
  19.             (l == null && r != null)
  21.         ) {
  22.             return false;
  23.         }
  24.         if (l != null) {
  25.             queue.add(l);
  26.         }
  27.         if (r != null) {
  28.             queue.add(r);
  29.         }
  30.         if (l == null || r == null) {
  31.             leaf = true;
  32.         }
  33.     }
  34.     return true;
  35. }
  1. public static boolean isCBT2(Node head) {
  2.     if (head == null) {
  3.         return true;
  4.     }
  5.     return process(head).isCBT;
  6. }
  8. private static Info process(Node head) {
  9.     if (head == null) {
  10.         return new Info(true, 0);
  11.     }
  12.     Info leftInfo = process(head.left);
  13.     Info rightInfo = process(head.right);
  14.     int highDiff = Math.abs(leftInfo.high - rightInfo.high);
  15.     boolean isCBT = leftInfo.isCBT && rightInfo.isCBT && highDiff < 2;
  17.     return new Info(isCBT, Math.max(leftInfo.high, rightInfo.high) + 1);
  18. }
  20. private static class Info {
  21.     //是否平衡二叉树
  22.     boolean isCBT;
  23.     //高度
  24.     int high;
  26.     public Info(boolean isCBT, int high) {
  27.         this.isCBT = isCBT;
  28.         this.high = high;
  29.     }
  30. }

2、如何判断一棵树是不是搜索二叉树

搜索二叉树：每一颗子树中，子树左边的值都比头小，子树右边的值都比头大 经典的搜索二叉树 没有重复值，如果需要处理重复值，则采用在相同值的节点内使用链表

  1. public static boolean isBST1(Node head) {
  2.     if (head == null) {
  3.         return true;
  4.     }
  5.     ArrayList<Node> arr = new ArrayList<>();
  6.     in(head, arr);
  7.     for (int i = 1; i < arr.size(); i++) {
  8.         if (arr.get(i).value <= arr.get(i - 1).value) {
  9.             return false;
  10.         }
  11.     }
  12.     return true;
  13. }
  15. public static void in(Node head, ArrayList<Node> arr) {
  16.     if (head == null) {
  17.         return;
  18.     }
  19.     in(head.left, arr);
  20.     arr.add(head);
  21.     in(head.right, arr);
  22. }
  1. public static boolean isBST2(Node head) {
  2.     if (head == null) {
  3.         return true;
  4.     }
  5.     return process(head).isBST;
  6. }
  8. public static class Info {
  9.     //是否搜索二叉树
  10.     public boolean isBST;
  11.     //左树中的最大值
  12.     public int max;
  13.     //右树中的最小值
  14.     public int min;
  16.     public Info(boolean i, int ma, int mi) {
  17.         isBST = i;
  18.         max = ma;
  19.         min = mi;
  20.     }
  22. }
  24. public static Info process(Node x) {
  25.     if (x == null) {
  26.         return null;
  27.     }
  28.     Info leftInfo = process(x.left);
  29.     Info rightInfo = process(x.right);
  30.     int max = x.value;
  31.     if (leftInfo != null) {
  32.         max = Math.max(max, leftInfo.max);
  33.     }
  34.     if (rightInfo != null) {
  35.         max = Math.max(max, rightInfo.max);
  36.     }
  37.     int min = x.value;
  38.     if (leftInfo != null) {
  39.         min = Math.min(min, leftInfo.min);
  40.     }
  41.     if (rightInfo != null) {
  42.         min = Math.min(min, rightInfo.min);
  43.     }
  44.     boolean isBST = true;
  45.     if (leftInfo != null && !leftInfo.isBST) {
  46.         isBST = false;
  47.     }
  48.     if (rightInfo != null && !rightInfo.isBST) {
  49.         isBST = false;
  50.     }
  51.     if (leftInfo != null && leftInfo.max >= x.value) {
  52.         isBST = false;
  53.     }
  54.     if (rightInfo != null && rightInfo.min <= x.value) {
  55.         isBST = false;
  56.     }
  57.     return new Info(isBST, max, min);
  58. }

给定一颗二叉树的头结点head，任何两个节点之间的都存在距离，返回整颗二叉树的最大距离

  1. public static int maxDistance2(Node head) {
  2.     return process(head).maxDistance;
  3. }
  5. public static class Info {
  6.     //子树最大距离
  7.     public int maxDistance;
  8.     //子树高度
  9.     public int height;
  11.     public Info(int m, int h) {
  12.         maxDistance = m;
  13.         height = h;
  14.     }
  16. }
  18. public static Info process(Node x) {
  19.     if (x == null) {
  20.         return new Info(0, 0);
  21.     }
  22.     Info leftInfo = process(x.left);
  23.     Info rightInfo = process(x.right);
  24.     int height = Math.max(leftInfo.height, rightInfo.height) + 1;
  25.     int p1 = leftInfo.maxDistance;
  26.     int p2 = rightInfo.maxDistance;
  27.     int p3 = leftInfo.height + rightInfo.height + 1;
  28.     int maxDistance = Math.max(Math.max(p1, p2), p3);
  29.     return new Info(maxDistance, height);
  30. }

判断一颗数是否是满二叉树

满二叉树：如果一课数的高度为h，则该树的节点数为2h-1

  1. // 第一种方法
  2. // 收集整棵树的高度h，和节点数n
  3. // 只有满二叉树满足 : 2 ^ h - 1 == n
  4. public static boolean isFull1(Node head) {
  5.     if (head == null) {
  6.         return true;
  7.     }
  8.     Info1 all = process1(head);
  9.     return (1 << all.height) - 1 == all.nodes;
  10. }
  12. public static class Info1 {
  13.     public int height;
  14.     public int nodes;
  16.     public Info1(int h, int n) {
  17.         height = h;
  18.         nodes = n;
  19.     }
  20. }
  22. public static Info1 process1(Node head) {
  23.     if (head == null) {
  24.         return new Info1(0, 0);
  25.     }
  26.     Info1 leftInfo = process1(head.left);
  27.     Info1 rightInfo = process1(head.right);
  28.     int height = Math.max(leftInfo.height, rightInfo.height) + 1;
  29.     int nodes = leftInfo.nodes + rightInfo.nodes + 1;
  30.     return new Info1(height, nodes);
  31. }
  1. // 第二种方法
  2. // 收集子树是否是满二叉树
  3. // 收集子树的高度
  4. // 左树满 && 右树满 && 左右树高度一样 -> 整棵树是满的
  5. public static boolean isFull2(Node head) {
  6.     if (head == null) {
  7.         return true;
  8.     }
  9.     return process2(head).isFull;
  10. }
  12. public static class Info2 {
  13.     public boolean isFull;
  14.     public int height;
  16.     public Info2(boolean f, int h) {
  17.         isFull = f;
  18.         height = h;
  19.     }
  20. }
  22. public static Info2 process2(Node h) {
  23.     if (h == null) {
  24.         return new Info2(true, 0);
  25.     }
  26.     Info2 leftInfo = process2(h.left);
  27.     Info2 rightInfo = process2(h.right);
  28.     boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
  29.     int height = Math.max(leftInfo.height, rightInfo.height) + 1;
  30.     return new Info2(isFull, height);
  31. }

给定一颗二叉树的头结点，返回这颗二叉树中最大的二叉搜索子树的头结点

  1. public static Node maxSubBSTHead2(Node head) {
  2.     if (head == null) {
  3.         return null;
  4.     }
  5.     return process(head).maxSubBSTHead;
  6. }
  8. // 每一棵子树
  9. public static class Info {
  10.     //最大搜索子树的头结点
  11.     public Node maxSubBSTHead;
  12.     //最大搜索子树的节点数
  13.     public int maxSubBSTSize;
  14.     //右树的最小值
  15.     public int min;
  16.     //左树的最大值
  17.     public int max;
  19.     public Info(Node h, int size, int mi, int ma) {
  20.         maxSubBSTHead = h;
  21.         maxSubBSTSize = size;
  22.         min = mi;
  23.         max = ma;
  24.     }
  25. }
  27. public static Info process(Node X) {
  28.     if (X == null) {
  29.         return null;
  30.     }
  31.     Info leftInfo = process(X.left);
  32.     Info rightInfo = process(X.right);
  33.     int min = X.value;
  34.     int max = X.value;
  35.     Node maxSubBSTHead = null;
  36.     int maxSubBSTSize = 0;
  37.     if (leftInfo != null) {
  38.         min = Math.min(min, leftInfo.min);
  39.         max = Math.max(max, leftInfo.max);
  40.         maxSubBSTHead = leftInfo.maxSubBSTHead;
  41.         maxSubBSTSize = leftInfo.maxSubBSTSize;
  42.     }
  43.     if (rightInfo != null) {
  44.         min = Math.min(min, rightInfo.min);
  45.         max = Math.max(max, rightInfo.max);
  46.         if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
  47.             maxSubBSTHead = rightInfo.maxSubBSTHead;
  48.             maxSubBSTSize = rightInfo.maxSubBSTSize;
  49.         }
  50.     }
  51.     if ((leftInfo == null ? true : (leftInfo.maxSubBSTHead == X.left && leftInfo.max < X.value))
  52.         && (rightInfo == null ? true : (rightInfo.maxSubBSTHead == X.right && rightInfo.min > X.value))) {
  53.         maxSubBSTHead = X;
  54.         maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
  55.             + (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
  56.     }
  57.     return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
  58. }