10. ＜ tag binary tree and BST foundation ＞ lt.700 Search in binary search tree + lt.98 Validate binary search tree + lt.530 Minimum absolute difference of binary search tree (the same as lt.783)

lt.700. Search in binary search tree

[ Case needs ]

[ Thought analysis ]

• This is a simple question worthy of the name
• BST: Binary search tree , For each node in the tree ,
• • The value of her left node is less than this node ,
• • The value of her right node is greater than this node ;
    

[ Code implementation one , Recursive method ]

class Solution {
    
    //1.  Recursive function ,  lookup BST,  Return value found node 
    public TreeNode searchBST(TreeNode root, int val) {
    
        //2.  Recursion end condition 
        if(root == null || root.val == val)return root;

        //3.  Single layer recursive logic 
        // if(root.val == val){
    
        // return root;
        // }else 
        if(root.val > val){
    
            return searchBST(root.left, val);
        }else{
    
            return searchBST(root.right, val);
        }
    }
}

Simplified edition

public TreeNode searchBST(TreeNode root, int val) {
    
    if (root == null || root.val == val) return root;
    return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}

[ Code implementation 2 , Iterative method ]

public TreeNode searchBST(TreeNode root, int val) {
    
    while (root != null && root.val != val) {
    
        root = root.val > val ? root.left : root.right;
    }
    return root;
}

lt.98. Verify binary search tree

[ Case needs ]

[ Train of thought analysis 1 , recursive ]

[ Code implementation ]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    //1.  Recursive function ,  Verify that each node is BST, 
        // Parameters :  The current node that is considered the root node 
        //  return :  It's still not 
    //long maxVal = Integer.MIN_VALUE; ---> -long,  great 

    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
    
       //2.  Recursive export 
       if(root == null)return true;

       //3.  Single layer recursive logic 
       // BST The middle order traversal in is an increasing sequence 
       boolean left = isValidBST(root.left); // The left subtree 
       
       if(pre != null && pre.val >= root.val){
    
           return false;
       }else{
    
           pre = root;
       }

       boolean right = isValidBST(root.right); // Right subtree 

       return left && right;
    }
}

[ Train of thought analysis II , aggregate + Recursive method ]

• Remember this sentence , For binary search tree (BST) Do middle order traversal , What you get is a sequence in ascending order
• So we can BST Do middle order traversal , While traversing, put the encountered number into the set ( Because the length is unknown , Unavailable array ), At the same time, compare whether the last number of the set and the number to be stored are in ascending order .

[ Code implementation ]

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    
    List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
    
        //1.  Put in collection 
        return dfs(root);
    }

    public boolean dfs(TreeNode root){
    
        //
        if(root == null)return true;

        // Single layer recursive logic 
        boolean left = dfs(root.left);

        // 1.  Set is not empty ,  And to be deposited root.val > list Last element of ,  ascend ,  That's right 
        if(!list.isEmpty() && list.get(list.size() - 1) < root.val){
    
            list.add(root.val);
        // 2.  Set is not empty ,  And to be deposited root.val <= list Last element of ,  Non ascending ,  This is not true 
        }else if(!list.isEmpty() && list.get(list.size() - 1) >= root.val){
    
            return false;
        }else{
    
            //3.  When the collection is empty ,  Store elements directly 
            list.add(root.val);
        }

        boolean right = dfs(root.right);


        return left && right;
    }
}

lt.530. The minimum absolute difference of binary search tree ( Same as lt.783)

[ Case needs ]

[ Train of thought analysis 1 , aggregate + recursive ]

[ Code implementation ]

class Solution {
    

    List<Integer> list = new ArrayList<>();
    int res = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
    
        if(root == null)return 0;

        getMinimumDifference(root.left);

        if(list.size() > 0){
    
            res = Math.min(res, root.val - list.get(list.size() - 1));
        }

        list.add(root.val);
        getMinimumDifference(root.right);

        return res;
    }
}

[ Train of thought analysis II , recursive + pre Record the last traversal node ]

[ Code implementation ]

//1.  recursive  +  Record the previous node 
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    //1.  Recursive function 
    int res = Integer.MAX_VALUE;
    TreeNode pre = null;
    public int getMinimumDifference(TreeNode root) {
    
        //2.  Recursive export 
        if(root == null)return 0;

        //3.  Single layer recursive logic ( In the sequence traversal )
        getMinimumDifference(root.left);

        if(pre != null){
    
            res = Math.min(res, root.val - pre.val);
        }

        pre = root;

        getMinimumDifference(root.right);

        return res;
    }
}