leetcode:98. Validate binary search tree

98. Verify binary search tree

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/validate-binary-search-tree/

Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .

It works The binary search tree is defined as follows ：

• The left subtree of the node contains only Less than Number of current nodes .
• The right subtree of the node contains only Greater than Number of current nodes .
• All left and right subtrees Oneself Must also be a binary search tree .

Example 1：

 Input ：root = [2,1,3]
 Output ：true

Example 2：

 Input ：root = [5,1,4,null,null,3,6]
 Output ：false
 explain ： The value of the root node is  5 , But the value of the right child node is  4 .

Tips ：

• The number of nodes in the tree ranges from $[1,10^4]$ Inside
• $-2^{31}$ <= Node.val <= $2^{31}-1$

solution

• In the sequence traversal + Sort comparison ： The middle order traversal of a binary search tree is an ordered sequence , You can traverse the middle order first , Then judge whether the middle order traversal sequence is orderly , And no repeating elements ;
• Middle order traversal recursion process for judgment ： The middle order traversal can be judged based on the fact that the elements of the left subtree are smaller than the root node , The nodes of the right subtree must be larger than the root node ; Here is a definition of prev Node as comparison , Then recursively traverse the middle order ;

Code implementation

In the sequence traversal + Compare after sorting

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        res = []

        if not root:
            return True

        def helper(node):
            if not node:
                return node
            
            helper(node.left)
            res.append(node.val)
            helper(node.right)

        helper(root)   
        return res == sorted(res) and len(set(res)) == len(res)

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
private:
    vector<int> res;
public:
    TreeNode* helper(TreeNode* node) {
    
        if (node == nullptr)
            return node;
        
        helper(node->left);
        res.push_back(node->val);
        helper(node->right);
        return node;
    }

    bool isValidBST(TreeNode* root) {
    
        helper(root);
        vector<int> res_copy = res;
        sort(res.begin(), res.end());
        set<int> s;
        for (int v: res_copy) {
    
            s.insert(v);
        }
        return res_copy == res && res_copy.size() == s.size();
    }
};

Complexity analysis

• Time complexity ： $O(NlogN)$ Time required for sorting
• Spatial complexity ： $O(N)$

In the sequence traversal

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def __init__(self):
        self.prev = None

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        if not self.isValidBST(root.left):
            return False
        
        if self.prev and self.prev.val >= root.val:  #  If the value of the node obtained by the middle order traversal is less than or equal to the previous  inorder, Description is not a binary search tree 
            return False
        
        self.prev = root

        return self.isValidBST(root.right)

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
private:
    TreeNode* prev = nullptr;

public:
    bool isValidBST(TreeNode* root) {
    
        if (root == nullptr)
            return true;
        
        if (not isValidBST(root->left))
            return false;
        
        if (prev != nullptr && prev->val >= root->val)  //  If the value of the node obtained by the middle order traversal is less than or equal to the previous  inorder, Description is not a binary search tree 
            return false;
        
        prev = root;

        return isValidBST(root->right);
    }
};

Complexity analysis

• Time complexity ： $O(N)$
• Spatial complexity ： $O(N)$

Reference resources

• https://www.geeksforgeeks.org/how-to-convert-a-vector-to-set-in-c/