题解 | #判断是不是二叉搜索树#

感觉还是有点难度的，我能想到的就三条路：

1. 递归。一开始我用递归写了一遍，发现仅仅用自顶向下的逻辑没办法排除下层以下的值比本结点大的情况，所以还得加一个变量去记录每层以各个结点为根的子树的最大值和最小值，如果这个过程也以递归来求，那时间空间成本都太大了，相当于两层循环。
2. 栈。虽然这是自底向上的逻辑，但也不好写，首先处理循环中如何不重复放入结点就很麻烦。其次，跟上面说的一样，需要用变量去记录最大最小值，记录的个数应该是2n。费劲巴拉的最后性能不好，得不偿失。
3. 转换为链表。因为二叉搜索树按特定规则转换为链表后应该是有序的，所以先转换为链表，再遍历检查就能知道原来的二叉树是否是搜索树。我这里转换代码就用的递归的方法，虽然也需要n的复杂度，但比方法一的递归好写太多。大道至简🙂

class Solution {
  public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (!pRootOfTree) return pRootOfTree;
        if (!pRootOfTree->left && !pRootOfTree->right) return pRootOfTree;
        TreeNode* head = pRootOfTree;
        TreeNode* lhead = pRootOfTree->left, * rhead = pRootOfTree->right;
        TreeNode* tail;
        if (lhead) {
            head = Convert(lhead);
            for (tail = head; tail->right; tail = tail->right);
            tail->right = pRootOfTree;
            pRootOfTree->left = tail;
        }
        if (rhead) {
            rhead = Convert(rhead);
            rhead->left = pRootOfTree;
            pRootOfTree->right = rhead;
        }
        return head;
    }

    bool isValidBST(TreeNode* root) {
        // write code here
        if (!root) return false;
        root = Convert(root); // 先按照二叉搜索树转换为双向链表
        TreeNode* tmp = root;
        while (root->right) {
            if (root->val > root->right->val) return false;
            root = root->right;
        }
        return true;
    }
};