最大BST子树

来源

解题思路(二叉树递归) #

本题有两个问题：找出二叉树中的为 BST 的子树，返回最大的那个 BST 子树的节点数。

因此，必须从叶子节点往根节点的方向遍历，即 DFS。

对于叶子节点来说，它本身就是一颗 BST，节点数为 1。

对于非叶子节 node 点来说，有以下情况：

1. 左右子节点为根节点的子树均为 BST，且 node 大于左子树的最大值，小于右子树的最小值，于是以 node 为根节点的树也是 BST，于是又找到一颗更大的 BST，节点数为左右子树结点数之和加一。

2. 当前节点 node 不满足构成 BST 的条件，于是只能从左右子树中找最大 BST。

class Solution {
 private:
  struct Info {
    int maxBSTSubtreeSize, allSize, max, min;
    Info(int maxBSTSubtreeSize, int allSize, int max, int min)
        : maxBSTSubtreeSize(maxBSTSubtreeSize),
          allSize(allSize),
          max(max),
          min(min){};
  };

  Info *process(Node *x) {
    if (x == nullptr) return nullptr;
    Info *lInfo = process(x->left);
    Info *rInfo = process(x->right);
    int ma = x->val, mi = x->val;
    int allSize = 1;
    if (lInfo != nullptr) {
      ma = max(ma, lInfo->max);
      mi = min(mi, lInfo->min);
      allSize += lInfo->allSize;
    }

    if (rInfo != nullptr) {
      ma = max(ma, rInfo->max);
      mi = min(mi, rInfo->min);
      allSize += rInfo->allSize;
    }

    int p1 = -1;
    if (lInfo != nullptr) {
      p1 = lInfo->maxBSTSubtreeSize;
    }
    int p2 = -1;
    if (rInfo != nullptr) {
      p2 = rInfo->maxBSTSubtreeSize;
    }

    int p3 = -1;
    bool leftBST =
        (lInfo == nullptr ? true
                          : (lInfo->maxBSTSubtreeSize == lInfo->allSize));
    bool rightBST =
        (rInfo == nullptr ? true
                          : (rInfo->maxBSTSubtreeSize == rInfo->allSize));

    if (leftBST && rightBST) {
      bool leftMaxLessX = (lInfo == nullptr ? true : (lInfo->max < x->val));
      bool rightMinMoreX = (rInfo == nullptr ? true : (x->val < rInfo->min));
      if (leftMaxLessX && rightMinMoreX) {
        int leftSize = lInfo == nullptr ? 0 : lInfo->allSize;
        int rightSize = rInfo == nullptr ? 0 : rInfo->allSize;
        p3 = leftSize + rightSize + 1;
      }
    }
    return new Info(max(p1, max(p2, p3)), allSize, ma, mi);
  }

 public:
  int largestBSTSubtree(Node *head) {
    if (head == nullptr) return 0;
    return process(head)->maxBSTSubtreeSize;
  }
};