是否为搜索二叉树

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

二叉树递归套路 #

1. 假设以 X 节点为头，假设可以向 X 左树和 X 右树要任何信息
2. 在上一步的假设下，讨论以 X 为头节点的树，得到答案的可能性（最重要）
3. 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4. 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息 S
5. 递归函数都返回 S，每一棵子树都这么要求
6. 在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息

class Solution {
 private:
  struct Info {
    bool isBST;
    int max, min;
    Info(bool bst, int max, int min) : isBST(bst), 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->value, mi = x->value;
    if (lInfo != nullptr) {
      ma = max(ma, lInfo->max);
      mi = min(mi, lInfo->min);
    }
    if (rInfo != nullptr) {
      ma = max(ma, rInfo->max);
      mi = min(mi, rInfo->min);
    }

    bool isBST = true;
    if (lInfo != nullptr && !lInfo->isBST) isBST = false;
    if (rInfo != nullptr && !rInfo->isBST) isBST = false;

    if (lInfo != nullptr && lInfo->max >= x->value) isBST = false;
    if (rInfo != nullptr && rInfo->min <= x->value) isBST = false;
    return new Info(isBST, ma, mi);
  }

 public:
  bool isBST(Node *head) {
    if (head == nullptr) return true;
    return process(head)->isBST;
  }
};