LeetCode 98 验证二叉搜索树

LeetCode 98 验证二叉搜索树

给一个二叉树,判断其是否是一个有效的二叉搜索树。

因为二叉搜索树的中序遍历结果是一个有序数组,我们可以将中序遍历的结果保存在一个数组中,再判断该数组是否是有序数组。有递归和迭代两种写法。时间复杂度是O(n),空间复杂度为O(n)。

// C++ recursion
class Solution {
    vector<int> arr;
public:
    bool isValidBST(TreeNode *root) {
        arr = vector<int>();
        InorderTraverse(root);
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] <= arr[i - 1])
                return false;
        }
        return true;
    }

    void InorderTraverse(TreeNode *node) {
        if (!node)
            return;
        InorderTraverse(node->left);
        arr.push_back(node->val);
        InorderTraverse(node->right);
    }
};
// C++ iteration
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root)
            return true;
        vector<int> arr;
        stack<TreeNode *> s;
        TreeNode *node = root;
        while (node || !s.empty()) {
            while (node) {
                s.push(node);
                node = node->left;
            }
            if (!s.empty()) {
                node = s.top();
                arr.push_back(node->val);
                s.pop();
                node = node->right;
            }
        }
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] <= arr[i - 1])
                return false;
        }
        return true;
    }
};

也可以通过二叉树的定义来实现,只需要依次判断当前节点大于左子树的最大值,小于右子树的最小值即可。有递归和迭代两种写法。时间复杂度是O(n),空间复杂度是O(n)。

// C++ recursion
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root)
            return true;
        return IsValidSubtree(root, nullptr, nullptr);
    }

    bool IsValidSubtree(TreeNode *node, const int *min_val, const int *max_val) {
        if (!node)
            return true;
        if ((min_val && *min_val >= node->val) || (max_val && *max_val <= node->val))
            return false;
        return IsValidSubtree(node->left, min_val, &(node->val)) && IsValidSubtree(node->right, &(node->val), max_val);
    }
};
// C++ iteration
class Solution {
public:
    bool isValidBST(TreeNode *root) {
        if (!root)
            return true;
        stack<tuple<TreeNode *, int *, int *>> s;
        s.push(make_tuple(root, nullptr, nullptr));
        while (!s.empty()) {
            auto curr = s.top();
            s.pop();
            auto node = get<0>(curr);
            auto &min_val = get<1>(curr), &max_val = get<2>(curr);
            if ((min_val && *min_val >= node->val) || (max_val && *max_val <= node->val))
                return false;
            if (node->left)
                s.push(make_tuple(node->left, min_val, &node->val));
            if (node->right)
                s.push(make_tuple(node->right, &node->val, max_val));
        }
        return true;
    }
};
# Python3 recursion
class Solution:
    def isValidBST(self, root: 'TreeNode') -> 'bool':
        if not root:
            return True
        return self.IsValidNode(root, None, None)
    
    def IsValidNode(self, node, min_val, max_val):
        if not node:
            return True
        if (min_val is not None and min_val >= node.val) or (max_val is not None and max_val <= node.val):
            return False
        return self.IsValidNode(node.left, min_val, node.val) and self.IsValidNode(node.right, node.val, max_val)
# Python3 iteration
class Solution:
    def isValidBST(self, root: 'TreeNode') -> 'bool':
        if not root:
            return True
        stack = [(root, None, None)]
        while stack:
            node, min_val, max_val = stack.pop()
            if (min_val is not None and min_val >= node.val) or (max_val is not None and max_val <= node.val):
                return False
            if node.left:
                stack.append((node.left, min_val, node.val))
            if node.right:
                stack.append((node.right, node.val, max_val))
        return True
comments powered by Disqus