leetcode--98.验证二叉搜索树、45.删除二叉搜索树中的节点、701.二叉搜索树中的插入操作

本文主要是介绍leetcode--98.验证二叉搜索树、45.删除二叉搜索树中的节点、701.二叉搜索树中的插入操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode–98.验证二叉搜索树

题目：给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

leetcode链接

代码：

public boolean isValidBST(TreeNode root) {return func(root,null,null);
}
public boolean func(TreeNode root, Integer lower,Integer upper){if(root ==null )return true;int val=root.val;if(lower !=null && val<=lower) return false;if(upper!=null && val>=upper) return false;if(!func(root.right,val,upper)) return false;if(!func(root.left,lower,val)) return false;return true;
}

leetcode–45.删除二叉搜索树中的节点

题目：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

思路：

如果 key > root.val，说明要删除的节点在右子树，root.right = deleteNode(root.right, key)。
如果 key < root.val，说明要删除的节点在左子树，root.left = deleteNode(root.left, key)。
如果 key == root.val，则该节点就是我们要删除的节点，则：
- 如果该节点是叶子节点，则直接删除它：root = null。
- 如果该节点不是叶子节点且有右节点，找到该节点右子树中最小的节点（最左下角的节点）
- 如果该节点不是叶子节点且只有左节点，找到该节点左子树中最大的节点（最右下角的节点）
返回 root

代码：

public int letf(TreeNode root){root=root.left;while (root.right!=null){root=root.right;}return root.val;
}
public int right(TreeNode root){root=root.right;while (root.left!=null){root=root.left;}return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {if(root==null)return null;if(key>root.val){root.right=deleteNode(root.right,key);}else if(key< root.val){root.left=deleteNode(root.left,key);}else {if(root.left==null && root.right==null) root=null;else if(root.right!=null){root.val=right(root);root.right=deleteNode(root.right,root.val);}else {root.val=letf(root);root.left=deleteNode(root.left,root.val);}}return root;
}

leetcode–701.二叉搜索树中的插入操作

题目：给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
leetcode链接
思路：

若 root == null，则返回 TreeNode(val)。
若 val > root.val，插入到右子树。
若 val < root.val，插入到左子树。
返回 root。

代码：

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