给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

c plus

  • 利用中序遍历是升序的特征验证

    1. class Solution {
    2. public:
    3.   bool isValidBST(TreeNode* root) {
    4.       TreeNode* prev = NULL;
    5.       return inorder(root, prev);       //prev 是最前面的那个节点，如果是传值的话，这里应该传最小值。要保存节点指针供上一层使用，所以用指针引用。
    6.   }
    7.   bool inorder(TreeNode *root, TreeNode* &prev) {
    8.       if (!root) return true;
    9.       if(!inorder(root->left, prev)) return false;
    10.       if (prev && (prev->val >= root->val)) return false;
    11.       prev = root;
    12.       return inorder(root->right, prev);
    13.   }
    14. };

  • 根据定义判断
    题解

    1. class Solution {
    2. public:
    3.   bool isValidBST(TreeNode* root) {
    4.       return helper(root, LONG_MIN, LONG_MAX); 
    5.   }
    6.   bool helper(TreeNode *root, long long low, long long up) {
    7.       if (!root) return true;
    8.       if (root->val <= low || root->val >= up) return false;
    9.       if (!helper(root->left, low, root->val)) return false;//左子树作为下个子树的上限
    10.       return helper(root->right, root->val, up);//右子树作为下个子树的下限
    11.   }
    12. };

%E7%BB%99%E5%AE%9A%E4%B8%80%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%A0%91%EF%BC%8C%E5%88%A4%E6%96%AD%E5%85%B6%E6%98%AF%E5%90%A6%E6%98%AF%E4%B8%80%E4%B8%AA%E6%9C%89%E6%95%88%E7%9A%84%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E3%80%82%0A%0A%E5%81%87%E8%AE%BE%E4%B8%80%E4%B8%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E5%85%B7%E6%9C%89%E5%A6%82%E4%B8%8B%E7%89%B9%E5%BE%81%EF%BC%9A%0A%0A%E8%8A%82%E7%82%B9%E7%9A%84%E5%B7%A6%E5%AD%90%E6%A0%91%E5%8F%AA%E5%8C%85%E5%90%AB%E5%B0%8F%E4%BA%8E%E5%BD%93%E5%89%8D%E8%8A%82%E7%82%B9%E7%9A%84%E6%95%B0%E3%80%82%0A%E8%8A%82%E7%82%B9%E7%9A%84%E5%8F%B3%E5%AD%90%E6%A0%91%E5%8F%AA%E5%8C%85%E5%90%AB%E5%A4%A7%E4%BA%8E%E5%BD%93%E5%89%8D%E8%8A%82%E7%82%B9%E7%9A%84%E6%95%B0%E3%80%82%0A%E6%89%80%E6%9C%89%E5%B7%A6%E5%AD%90%E6%A0%91%E5%92%8C%E5%8F%B3%E5%AD%90%E6%A0%91%E8%87%AA%E8%BA%AB%E5%BF%85%E9%A1%BB%E4%B9%9F%E6%98%AF%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E3%80%82%0A%0A%23%23%23%20c%20plus%0A%0A%20%E5%88%A9%E7%94%A8%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%E6%98%AF%E5%8D%87%E5%BA%8F%E7%9A%84%E7%89%B9%E5%BE%81%E9%AA%8C%E8%AF%81%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20bool%20isValidBST(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20TreeNode%20prev%20%3D%20NULL%3B%0A%20%20%20%20%20%20%20%20return%20inorder(root%2C%20prev)%3B%20%20%20%20%20%20%20%2F%2Fprev%20%E6%98%AF%E6%9C%80%E5%89%8D%E9%9D%A2%E7%9A%84%E9%82%A3%E4%B8%AA%E8%8A%82%E7%82%B9%EF%BC%8C%E5%A6%82%E6%9E%9C%E6%98%AF%E4%BC%A0%E5%80%BC%E7%9A%84%E8%AF%9D%EF%BC%8C%E8%BF%99%E9%87%8C%E5%BA%94%E8%AF%A5%E4%BC%A0%E6%9C%80%E5%B0%8F%E5%80%BC%E3%80%82%E8%A6%81%E4%BF%9D%E5%AD%98%E8%8A%82%E7%82%B9%E6%8C%87%E9%92%88%E4%BE%9B%E4%B8%8A%E4%B8%80%E5%B1%82%E4%BD%BF%E7%94%A8%EF%BC%8C%E6%89%80%E4%BB%A5%E7%94%A8%E6%8C%87%E9%92%88%E5%BC%95%E7%94%A8%E3%80%82%0A%20%20%20%20%7D%0A%20%20%20%20bool%20inorder(TreeNode%20root%2C%20TreeNode%20%26prev)%20%7B%0A%20%20%20%20%20%20%20%20if%20(!root)%20return%20true%3B%0A%20%20%20%20%20%20%20%20if(!inorder(root-%3Eleft%2C%20prev))%20return%20false%3B%0A%20%20%20%20%20%20%20%20if%20(prev%20%26%26%20(prev-%3Eval%20%3E%3D%20root-%3Eval))%20return%20false%3B%0A%20%20%20%20%20%20%20%20prev%20%3D%20root%3B%0A%20%20%20%20%20%20%20%20return%20inorder(root-%3Eright%2C%20prev)%3B%0A%20%20%20%20%7D%0A%7D%3B%0A%60%60%60%0A%0A%20%E6%A0%B9%E6%8D%AE%E5%AE%9A%E4%B9%89%E5%88%A4%E6%96%AD%0A%20%20%20%0A%20%20%20%5B%E9%A2%98%E8%A7%A3%5D(https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Fvalidate-binary-search-tree%2Fsolution%2Fyi-zhang-tu-rang-ni-ming-bai-shang-xia-jie-zui-da-%2F)%0A%60%60%60c%0Aclass%20Solution%20%7B%0Apublic%3A%0A%20%20%20%20bool%20isValidBST(TreeNode%20root)%20%7B%0A%20%20%20%20%20%20%20%20return%20helper(root%2C%20LONG_MIN%2C%20LONG_MAX)%3B%20%0A%20%20%20%20%7D%0A%20%20%20%20bool%20helper(TreeNode%20root%2C%20long%20long%20low%2C%20long%20long%20up)%20%7B%0A%20%20%20%20%20%20%20%20if%20(!root)%20return%20true%3B%0A%20%20%20%20%20%20%20%20if%20(root-%3Eval%20%3C%3D%20low%20%7C%7C%20root-%3Eval%20%3E%3D%20up)%20return%20false%3B%0A%20%20%20%20%20%20%20%20if%20(!helper(root-%3Eleft%2C%20low%2C%20root-%3Eval))%20return%20false%3B%2F%2F%E5%B7%A6%E5%AD%90%E6%A0%91%E4%BD%9C%E4%B8%BA%E4%B8%8B%E4%B8%AA%E5%AD%90%E6%A0%91%E7%9A%84%E4%B8%8A%E9%99%90%0A%20%20%20%20%20%20%20%20return%20helper(root-%3Eright%2C%20root-%3Eval%2C%20up)%3B%2F%2F%E5%8F%B3%E5%AD%90%E6%A0%91%E4%BD%9C%E4%B8%BA%E4%B8%8B%E4%B8%AA%E5%AD%90%E6%A0%91%E7%9A%84%E4%B8%8B%E9%99%90%0A%20%20%20%20%7D%0A%7D%3B%0A%0A%60%60%60%0A%0A