98. Validate Binary Search Tree
验证给定二叉树是否是二叉搜索树,个人认为属于面试题中的高频题目。
首先我们用最直观 最暴力 最ugly的代码先AC(中序遍历,验证vector中是否有重复元素 是否是升序):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        vector<int> inorder;
        inorder_bst(root,inorder);
        vector<int> sorted(inorder);
        sort(sorted.begin(),sorted.end());
        vector<int>::iterator it = unique(sorted.begin(),sorted.end());
        sorted.erase(it,sorted.end());
        if(sorted.size() != inorder.size())
            return false;
        
        if (equal(inorder.begin(), inorder.begin() + inorder.size(), sorted.begin()))
            return true;
            
        return false;
    }
    
private:
void inorder_bst(TreeNode * root,vector<int> & inorder)
{
    if(root == NULL)
        return;
    inorder_bst(root->left,inorder);
    inorder.push_back(root->val);
    inorder_bst(root->right,inorder);
}
};

运行效率有点意外,就这居然击败了近一半人的提交:

Runtime: 20 ms, faster than 45.02% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 22.3 MB, less than 93.69% of C++ online submissions for Validate Binary Search Tree.

学习讨论区中的解法,一个非常巧妙的算法如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBST(root,NULL,NULL);
    }
private:
    bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
        if(!root) return true;
        if(minNode && root->val <= minNode->val ||
           maxNode && root->val >= maxNode->val)
            return false;
        
        return isValidBST(root->left,minNode,root) && isValidBST(root->right,root,maxNode);
    }
};

这里巧妙的利用了两个参数保存最小结点和最大结点,利用二叉搜索树的特性,左子树所有元素都小于根节点,右子树所有元素都大于根节点,左子树不指定下限,右子树不指定上限。
运行效率:

Runtime: 12 ms, faster than 93.30% of C++ online submissions for Validate Binary Search Tree.
Memory Usage: 22 MB, less than 93.69% of C++ online submissions for Validate Binary Search Tree.

另一种巧妙解法,通过维护一个prev,保存中序遍历后的前一个元素,如果前一个元素大于等于当前节点那么则不是二叉搜索树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode * prev = NULL;
        return validate(root,prev);
    }
private:
    bool validate(TreeNode* node, TreeNode* &prev) {
        if(!node) return true;
        if(!validate(node->left,prev)) return false;
        if(prev && prev->val >= node->val) return false;
        prev = node;
        return validate(node->right,prev);
    }
};

通过这道题对递归有了进一步的理解,对比本文自己手写的方法一,简直不知道高几个level。年轻人还是too young too naive。
C++ in-order traversal, and please do not rely on buggy INT_MAX, INT_MIN solutions any more