最大的二叉搜索子树的头节点

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

二叉树递归套路 #

1. x 无关（x 不是最低的汇聚点）
   • 左子树上有答案
   • 右子树上有答案
   • ab 不双全
2. x 是答案
   • 左子树有 a、b 中一个，右子树有 a、b 中一个，在 x 处汇聚
   • x 本身是 a，在左右子树中发现 b
   • x 本事是 b，在左右子树中发现 a

public static Node maxSubBSTHead2(Node head) {
  if (head == null)
    return null;

  return process(head).maxSubBSTHead;
}

private static class Info {
  public Node maxSubBSTHead;
  public int maxSubBSTSize;
  public int min;
  public int max;

  public Info(Node h, int size, int mi, int ma) {
    maxSubBSTHead = h;
    maxSubBSTSize = size;
    min = mi;
    max = ma;
  }
}

public static Info process(Node x) {
  if (x == null)
    return null;

  Info lInfo = process(x.left);
  Info rInfo = process(x.right);
  int min = x.value;
  int max = x.value;
  Node maxSubBSTHead = null;
  int maxSubBSTSize = 0;
  if (lInfo != null) {
    min = Math.min(min, lInfo.min);
    max = Math.max(max, lInfo.max);
    maxSubBSTHead = lInfo.maxSubBSTHead;
    maxSubBSTSize = lInfo.maxSubBSTSize;
  }
  if (rInfo != null) {
    min = Math.min(min, rInfo.min);
    max = Math.max(max, rInfo.max);
    if (rInfo.maxSubBSTSize > maxSubBSTSize) {
      maxSubBSTHead = rInfo.maxSubBSTHead;
      maxSubBSTSize = rInfo.maxSubBSTSize;
    }
  }
  if ((lInfo == null ? true : (lInfo.maxSubBSTHead == x.left && lInfo.max < x.value))
      && (rInfo == null ? true : (rInfo.maxSubBSTHead == x.right && rInfo.min > x.value))) {
    maxSubBSTHead = x;
    maxSubBSTSize = (lInfo == null ? 0 : lInfo.maxSubBSTSize)
        + (rInfo == null ? 0 : rInfo.maxSubBSTSize) + 1;
  }
  return new Info(maxSubBSTHead, maxSubBSTSize, min, max);
}