Bst

30 Jun 2022

1.判断BST是否合法

​ 需要使用辅助函数，增加函数参数列表，在参数中携带额外信息，将约束传递给子树的所有节点。

 boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
	/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
    boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        if (root == null) return true;
        // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
        if (max != null && root.val >= max.val) return false;
        if (min != null && root.val <= min.val) return false;
         // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
        return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
    }

2.在BST中搜索一个数

    TreeNode searchBST(TreeNode root, int target) {
        if (root == null) return null;

        //比root小到左子树搜索
        if (root.val < target) return searchBST(root.left, target);
        //比root大到右子树搜索
        if (root.val > target) return searchBST(root.right, target);
        //root.val == target
        return root;
    }

3.在BST中插入一个数

一旦涉及「改」，就类似二叉树的构造问题，函数要返回 TreeNode 类型，并且要对递归调用的返回值进行接收。

    TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }

4.在BST中删除一个数

 //右子树最小节点替换实现
    TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            //只有单个子节点或者没有子节点
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            //左右都有节点
            //获得右子树的最小节点
            TreeNode minNode = getMin(root.right);
            //删除右子树最小的节点
            root.right = deleteNode(root.right, minNode.val);
            //用最小节点代替root节点
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

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

    //左子树最大节点替换实现
    TreeNode deleteNodeByleft(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            //找到左子树的最大节点
            TreeNode maxNode = getMax(root.left);
            //删除左子树的最大节点
            root.left = deleteNode(root.left, maxNode.val);
            //用左子树的最大节点替换root节点
            maxNode.left = root.left;
            maxNode.right = root.right;
            root = maxNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMax(TreeNode root) {
        while (root.right != null) root = root.right;
        return root;
    }
}