98. 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

class Solution {
  bool helper(TreeNode *TN, int64_t Lower, int64_t Upper) {
    if (!TN)
      return true;
    if (TN->val <= Lower || TN->val >= Upper)
      return false;
    return helper(TN->left, Lower, TN->val) && helper(TN->right, TN->val, Upper);
  }
public:
  bool isValidBST(TreeNode *root) {
    return helper(root, numeric_limits<int64_t>::min(),
                  numeric_limits<int64_t>::max());
  }
};

你会发现这个题目的思路其实非常类似于二分？尤其是设定上下界并且在每次向下分配的时候都更新相应的上下界的操作。实际上这个题跟101. 对称二叉树应该还有一点关系，因为你可以发现它这里采用的是向两侧 dispatch 的方案，而不是传统的递归中序遍历方案。

此外，它是可以被转成迭代进行的，这应该和后根遍历与中序遍历的等价性是有关系的。

二刷

class Solution {
  std::optional<int> Previous;
public:
  bool isValidBST(TreeNode* root) {
    if (!root)
      return true;

    bool Left = isValidBST(root->left);
    if (Previous) {
      bool Valid = Previous < root->val;
      if (!Valid)
        return false;
    }
    Previous = root->val;
    bool Right = isValidBST(root->right);
    return Left && Right;
  }
};

没什么好说的。中序有序是 BST 的关键性质。我觉得我这里这个 std::optional 用得还是挺巧妙的。

但是这个迭代法还是他妈的一如既往地丑啊。绕得要命，还不知道该怎么写。

class Solution {
public:
  bool isValidBST(TreeNode* root) {
    if (!root)
      return true;
    std::stack<TreeNode *> Stack;
    std::optional<int> Previous;
    while (root || !Stack.empty()) {
      while (root) {
        Stack.push(root);
        root = root->left;
      }
      root = Stack.top();
      Stack.pop();
      if (Previous) {
        if (!(Previous < root->val))
          return false;
      }
      Previous = root->val;
      root = root->right;
    }
    return true;
  }
};

背吧，没办法。硬要理解记忆的话，那么就像下面这样：

外层循环里 !Stack.empty() 的意思其实是「还有余下的递归层数」；

看到 root != nullptr 就一直往左走的来源是中序遍历上来啥都不干，先递归左子树——可以回想一下递归的中序遍历写法；

退出 while (root) 就是中序遍历碰到不动点了，也就是 if (!root) return {};，然后 Stack.pop() 退栈，考察右子树。

考察右子树的时候，根节点不用再入栈的原因是反正这棵子树的根节点都已经走完了，留着这层栈也没什么用了，不如直接跳层回溯到上一层。

哎，其实也就那样吧。但是难记也是真的。

三刷

class Solution {
public:
  bool isValidBST(TreeNode* root) {
    stack<TreeNode *> S;
    int64_t Last = LONG_MIN;
    while (root || !S.empty()) {
      while (root) {
        S.push(root);
        root = root->left;
      }
      root = S.top();
      S.pop();

      // Visit
      if (root->val <= Last)
        return false;
      Last = root->val;

      root = root->right;
    }
    return true;
  }
};

把这个pattern再默写一遍。