leetcode 98 - Validate Binary Search Tree

发布时间：2020-12-14 05:09:24 所属栏目：大数据来源：网络整理

导读：Given a binary tree,determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node‘s key. The right subtree of a node contains only node

Given a binary tree,determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node‘s key.
The right subtree of a node contains only nodes with keys greater than the node‘s key.
Both the left and right subtrees must also be binary search trees.

时间空间均超70%的方法，写的有点复杂：

思路是，当前节点左右都满足BST的条件下，还要顺便找出左子树的最大值leftMax和右子树的最小值rightMin，以防leftMax大于root->val或rightMin 小于 root->val

class Solution
{
public:
    bool isValidBST(TreeNode *root)
    {
        int subLeftMax = INT_MIN,subLeftMin = INT_MAX,subRightMax = INT_MIN,subRightMin = INT_MAX;

        return this->doValid(root,&subLeftMax,&subLeftMin,&subRightMax,&subRightMin);
    }

protected:
    bool doValid(TreeNode *root,int *leftMaxVal,int *leftMinVal,int *rightMaxVal,int *rightMinVal)
    {
        bool result = true;

        int subLeftMax = INT_MIN,subRightMin = INT_MAX;

        if (root == NULL || (root->left == NULL && root->right == NULL))
        {
            return true;
        }

        if ((root->left != NULL && root->left->val >= root->val) ||
            (root->right != NULL && root->right->val <= root->val))
        {
            return false;
        }

        result = this->doValid(root->left,&subRightMin);

        if (result == false || (root->left != NULL && subLeftMax >= root->val)
            || (root->left != NULL && subRightMax >= root->val))
        {
            return false;
        }

        *leftMaxVal = max(max(subLeftMax,subRightMax),(root->left == NULL ? INT_MIN : root->left->val));
        *leftMinVal = min(min(subLeftMin,subRightMin),(root->left == NULL ? INT_MAX : root->left->val));

        subLeftMax = subRightMax = INT_MIN;
        subLeftMin = subRightMin = INT_MAX;

        result = this->doValid(root->right,&subRightMin);

        if (result == false || (root->right != NULL && subLeftMin <= root->val)
            || (root->right != NULL &&subRightMin <= root->val))
        {
            return false;
        }

        *rightMaxVal = max(max(subLeftMax,(root->right == NULL ? INT_MIN : root->right->val));
        *rightMinVal = min(min(subLeftMin,(root->right == NULL ? INT_MAX : root->right->val));

        return  true;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!