[fun] summary of 3 clean C++ solutions


  • 0

    my first wrong implementation

    Wrong Reasons: I only consider the left node but not the all left
    sub-tree

     class Solution {
        public:
            bool isValidBST(TreeNode* root) {
                if(!root)   return true;
                if(root->left!=NULL && root->right!=NULL){
                    return root->left->val < root->val && root->right->val > root->val
                        && isValidBST(root->left) && isValidBST(root->right);
                }  
                else if(root->left!=NULL && root->right==NULL){
                    return root->left->val < root->val && isValidBST(root->left);
                } 
                else if(root->left==NULL && root->right!=NULL){
                    return root->right->val > root->val && isValidBST(root->right);
                } 
                else{
                    return true;
                }
            }
        };
    

    max-value & min-value based implementation we use the min-val and
    max-val to record the range scope of the root-left-sub-tree and
    root-right-sub-tree

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
            return help(root, LONG_MIN, LONG_MAX);
        }
        
        bool help(TreeNode* root, long min, long max){
            if(!root)   return true;
            if(root->val <= min || root->val >= max)  return false;
            return help(root->left, min, root->val) && help(root->right, root->val, max);
        }
    };
    

    in-order-traverse-based-comparision-with-previous-node-value

    class Solution {
    private:
        TreeNode* prev=NULL;
    public:
        bool isValidBST(TreeNode* root) {
            if(!root)   return true;
            return isValidBST(root->left)  && help(root) && isValidBST(root->right);
        }
        
        bool help(TreeNode* root){
            if(!prev){
                prev=root;
                return true;
            }
            if(prev->val >= root->val)   return false;
            prev=root;
            return true;
        }
    };

  • 0

    We must use the LONG_MIN and LONG_MAX to avoid the overflow problem of the INT_MAX and INT_MIN related.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.