98. Verify the binary search tree ●●

98. Verify binary search tree ●●

describe

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 themselves must also be binary search trees .

Example

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 .

Answer key

nature ： Middle order traversal , The value of the output binary search tree node is an ordered sequence .

Therefore, you can traverse in order and record all elements with an array , Then traverse the array to judge .

But it can also overall situation Define a Value to be compared , Directly in the middle order traversal process Comparative judgment And constantly update the value to be compared , It should be noted that ：

You cannot simply compare that the left node is smaller than the middle node , The right node is larger than the middle node , What we want to compare is All nodes of the left subtree Smaller than the intermediate node , All nodes in the right subtree Larger than the intermediate node , Therefore, compare with the previous nodes .

1. In the sequence traversal recursive

• Initialize the value to be compared to long long Type min , Deal with the situation that there is an integer minimum in the question ;

class Solution {
    
public:
    long long preValue = LONG_MIN;              //  The previous number before initialization is the long minimum 
    bool isValidBST(TreeNode* root) {
    
        if(!root) return true;
        bool left = isValidBST(root->left);     //  Left 
        if(root->val <= preValue){
                  //  in 
            return false;                       //  When traversing the middle order, compare with the previous number to judge the order 
        }else{
    
            preValue = root->val;       
        }
        bool right = isValidBST(root->right);   //  Right 
        return left && right;                   //  Effectiveness of left and right subtrees 
    }
};

• Or define the value to be compared as the node type

class Solution {
    
public:
    TreeNode* preNode = nullptr;              //  Nodes to be compared 
    bool isValidBST(TreeNode* root) {
    
        if(!root) return true;
        bool left = isValidBST(root->left);     //  Left 
        if(preNode != nullptr && root->val <= preNode->val){
          //  in 
            return false;                       //  Invalid , sign out 
        }else{
    
            preNode = root;                     //  When traversing the middle order, compare with the previous number to judge the order 
        }
        bool right = isValidBST(root->right);   //  Right 
        return left && right;                   //  Effectiveness of left and right subtrees 
    }
};

2. In the sequence traversal iteration

class Solution {
    
public:
    bool isValidBST(TreeNode* root) {
    
        stack<TreeNode*> st;
        TreeNode* preNode = nullptr;              //  Nodes to be compared 
        TreeNode* curr = root;
        while(curr != nullptr || !st.empty()){
    
            if(curr){
    
                st.push(curr);              //  Nodes on the stack 
                curr = curr->left;          //  The node pointer points to the left child 
            }else{
                              //  Traverse all left children 
                curr = st.top();            
                st.pop();                   //  in 
                if(preNode && curr->val <= preNode->val) return false;
                preNode = curr;
                curr = curr->right;         //  The node pointer points to the right child 
            }
        }
        return true;
    }
};

• utilize Null pointer marker Unified iterative writing of

class Solution {
    
public:
    bool isValidBST(TreeNode* root) {
    
        stack<TreeNode*> st;
        TreeNode* curr = nullptr;
        TreeNode* preNode = nullptr;    //  The former element , Nodes to be compared 
        st.push(root);
        while(!st.empty()){
    
            curr = st.top();
            st.pop();                   //  Visit children who are not at the top of the empty stack 
            if(curr != nullptr){
            //  The stack order is ： Right - in -null- Left ;  The stack order is ： Left -null- in - Right 
                if(curr->right) st.push(curr->right);
                st.push(curr);
                st.push(nullptr);
                if(curr->left) st.push(curr->left); 
            }else{
    
                curr = st.top();        // null The following elements indicate that you have visited , At this point, you need to pop up and take out the element value 
                st.pop();
                if(preNode != nullptr && curr->val <= preNode->val) return false;
                preNode = curr;
            }
        }
        return true;
    }
};