搜索二叉树（增删查）

验证搜索二叉树

题目链接

这个题目很坑，不是只比较每个节点的左右孩子满足左小右大，而是整棵树！，知道BST的中序遍历是有序的，思路打开，可以中序遍历二叉树然后判断结果是不是有序的，有序就是搜索二叉树，否则不是。有两个方法：①可以用一个变量max来记录最大值 ②遍历过程中直接比较前后节点

/**
 * 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 {
    //方法二：遍历过程中，前后节点比较
    public boolean isValidBST(TreeNode root) {
       return traverse(root);
    }
    TreeNode preNode=null;
    //二叉树的分解思路
    //定义：判以root为根的是是不是搜索二叉树
    boolean traverse(TreeNode root){
        if(root==null){
            return true;
        }   
        //判断左子树是不是搜索二叉树
        boolean left= traverse(root.left);
        //前一个节点与当前节点的比较
        if(preNode!=null&&preNode.val>=root.val){
        return false;
        }
        preNode=root;//第二次来root节点，记录此时节点作为前一个节点，继续往后遍历
        //判断右子树是不是搜索二叉树
        boolean right= traverse(root.right);

        return left&&right;
    }
}

/**
 * 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 {
    //方法一：增加一个变量max
    public boolean isValidBST(TreeNode root) {
       return traverse(root);
    }
    long  max=Long.MIN_VALUE;
    //二叉树的分解思路
    //定义：判以root为根的是是不是搜索二叉树
    boolean traverse(TreeNode root){
        if(root==null){
            return true;
        }   
        
       boolean left= traverse(root.left);

        if(max<root.val){
            max=root.val;
        }else{
            return false;
        }

        boolean right= traverse(root.right);

        return left&&right;
    }
}

二叉搜索树中的插入操作

题目链接

/**
 * 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 {
    //二叉树分解的思路
    //定义：在root为根的树中插入一个val节点
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root==null){
            return new TreeNode(val);
        }
        if(root.val<val){
            //去右子树插入val节点，将插好的树接到root的右子树上
           root.right = insertIntoBST(root.right,val);
        }
        if(root.val>val){
            //去左子树插入val节点，将插好的树接到root的左子树上
            root.left=insertIntoBST(root.left,val);
        }
        //最后返回root节点即可
        return root;
    }
}

删除指定节点（难）

题目链接

/**
 * 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 {
    //首先找到要删的节点
    //判断节点的孩子，有三种情况，①没有孩子②只有子树③有左右子树
    //deleteNode()定义：删除root为根的树中节点为k的节点
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if(root.val<key){
            //去右子树删
           root.right= deleteNode(root.right,key);
        }
        if(root.val>key){
            //去左子树删
           root.left= deleteNode(root.left,key);
        }
        //找到了目标节点
        if(root.val==key){
            // 排除了情况 1 之后
            if (root.left == null) {
            return root.right;
            }
            if (root.right == null){
            return root.left;
            } 
            //有左子树和右子树，先找右子树中最小的节点min
           TreeNode min= findMin(root.right);
           //然后将最小值赋给root
           root.val=min.val;
           //最后删除最小节点min
           root.right= deleteNode(root.right,min.val);
        }
            
        return root;
    }

    TreeNode findMin(TreeNode root){
    TreeNode min=root;
        while(root.left!=null){
            min=root.left;
            root=min;
        }
        return min;
    }
}