二叉搜索树系列

1. 判断是否为二叉搜索树

public boolean isBinaryTree(TreeNode root, TreeNode min, TreeNode max) { if(root == null) return true; if(min != null && root.val <= min.val) return false; if(max != null && root.val >= max.val) return false; return isBinaryTree(root.left, min, root) && isBinaryTree(root.right, root, max); } class Solution { long min = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root == null) return true; if(isValidBST(root.left) && root.val > min) { min = root.val; return isValidBST(root.right); } else return false; } }

2. 判断一个树是否存在

boolean isInBST(TreeNode root, int target) { if(root == null) return false; if(root.val == target) return true; if(target < root.val) return isInBST(root.left, target); if(target > root.val) return isInBST(root.right, target); }

3. 插入节点

root为空，返回一个值为val的新节点root不为空： val < root.val：插入到左子树val > root.val：插入到右子树 TreeNode insert(TreeNode root, int val) { if(root == null) return new TreeNode(val); if(val < root.val) root.left = insert(root.left, val); if(val > root.val) root.right = insert(root.right, val); return root; }

4. 删除元素

当找到节点时： 如果左右子树都为null，返回null如果一个子树为空，返回不为空的子树如果子树都不为空，找到右子树中的最小值，作为根节点的值，然后删除该节点 val小于当前节点值：遍历左子树val大于当前节点值：遍历右子树 TreeNode delete(TreeNode root, int val) { if(root == null) return null; if(root.val == val) { if(root.left == null) return right; if(root.right == null) return left; root.val = getMin(root.right).val; root.right = delete(root.right, root.val); } else if(val < root.val) root.left = delete(root.left, val); else if(val > root.val) root.right = delete(root.right, val); } TreeNode getMin(TreeNode root) { // BST 最左边的就是最小的 while(root.left != null) root = root.left; return root; }