A solution that calculate the previous value out explicitly


  • 0
    B

    It's enssentially the same with the standard solution as many others', but check it out:

    class Solution {
    public:
        bool isValidBST(TreeNode* root) {
    		if(root == NULL) return true;
    		bool ans = true;
    		TreeNode *tmp;
    		if(root->left != NULL) {
    			tmp = root->left;
    			while(tmp->right) {
    				tmp = tmp->right;
    			}// max value of left tree.
    		   	ans = ans && root->val > tmp->val;
    		}
    		if(root->right != NULL) {
    			tmp = root->right;
    			while(tmp->left) {
    				tmp = tmp->left;
    			}// min value of right tree.
    			ans = ans && root->val < tmp->val;
    		}
    		return ans && isValidBST(root->left) && isValidBST(root->right);
        }
    };
    

    Although my solution seems to be O(nlogn), it turns out as fast as the O(n) solution.


Log in to reply
 

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