Leetcode skimming: binary tree 21 (verifying binary search tree)

98. Verify binary search tree

Force button topic link

Given a binary tree , Determine whether it is an effective binary search tree .

Suppose a binary search tree has the following characteristics ：

• The left subtree of a node contains only the number of nodes smaller than the current node .
• The right subtree of a node contains only the number of nodes greater than the current node .
• All left and right subtrees themselves must also be binary search trees .

Traverse the middle order of the binary tree , Then traverse the result set , If the result set is in ascending order , It is a binary search tree , Because the nature of binary search tree is The middle order traversal is non decreasing . Tips for this question Ask for incremental , So there will be no equality .

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/** * @ClassName IsValidBST * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 21:32 * @Version 1.0 * https://leetcode.cn/problems/validate-binary-search-tree/ * 98.  Verify binary search tree  **/
public class IsValidBST {
    
    /** *  Direct middle order traversal to obtain the result  *  If the result is   Increasing , Then the verification is successful  * * @param root * @return */
    public boolean isValidBST(TreeNode root) {
    
        if (root.left == null && root.right == null) {
    
            return true;
        }
        Deque<Integer> deque = new ArrayDeque<Integer>();
        inorderTraversal(root, deque);
        Integer pre = deque.poll();
        Integer last = null;
        // Compare the previous value with the latter value , If not in ascending order , Is not a binary search tree 
        while (!deque.isEmpty()) {
    
            last = deque.poll();
            if (pre >= last) {
    
                return false;
            } else {
    
                pre = last;
            }
        }
        return true;
    }

    public void inorderTraversal(TreeNode root, Deque<Integer> deque) {
    
        if (root == null) {
    
            return;
        }
        // In the sequence traversal   Left   in   Right 
        inorderTraversal(root.left, deque);
        deque.offer(root.val);
        inorderTraversal(root.right, deque);
    }

}