Leetcode701450669中，如何实现二叉搜索树的插入、删除和修剪操作？
- 内容介绍
- 文章标签
- 相关推荐
本文共计753个文字，预计阅读时间需要4分钟。
二叉搜索树的插入删除修剪+Leetcode701-二叉搜索树中的插入操作+给定二叉搜索树（BST）的根节点+root+和要插入树中的值+value+，将值插入到二叉搜索树中。+返回插入后二叉搜索树的根节点。
二叉搜索树的插入删除修剪
Leetcode701-二叉搜索树中的插入操作
- 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
- 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
- 输入：root = [4,2,7,1,3], val = 5
- 输出：[4,2,7,1,3,5]
public TreeNode insertIntoBST(TreeNode root, int val) {
return insert(root,val);
}
public TreeNode insert(TreeNode root,int val){
if(root==null){
return new TreeNode(val);
}
if(root.val>val){
root.left=insert(root.left,val);
}
if(root.val<val){
root.right=insert(root.right,val);
}
return root;
}
Leetcode450-删除二叉搜索树中的节点
- 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
- 输入：root = [5,3,6,2,4,null,7], key = 3
- 输出：[5,4,6,2,null,null,7]
public TreeNode deleteNode(TreeNode root, int key) {
root=delete(root, key);
return root;
}
private TreeNode delete(TreeNode root, int key) {
if(root==null){
return null;
}
if(root.val>key){
root.left=delete(root.left,key);
}
else if(root.val<key){
root.right=delete(root.right,key);
}
else{
if(root.left==null){
return root.right;
}
if(root.right==null){
return root.left;
}
TreeNode temp=root.right;
while(temp.left!=null){
temp=temp.left;
}
root.val=temp.val;
root.right=delete(root.right,temp.val);
}
return root;
}
Leetcode669-修剪二叉搜索树
- 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案
- 输入：root = [1,0,2], low = 1, high = 2
- 输出：[1,null,2]
public TreeNode trimBST(TreeNode root, int low, int high) {
return trim(root,low,high);
}
public TreeNode trim(TreeNode root,int low,int high){
if(root==null){
return null;
}
if(root.val<low){
return trim(root.right,low,high);
}
if(root.val>high){
return trim(root.left,low,high);
}
root.left=trim(root.left,low,high);
root.right=trim(root.right,low,high);
return root;
}
本文共计753个文字，预计阅读时间需要4分钟。
二叉搜索树的插入删除修剪+Leetcode701-二叉搜索树中的插入操作+给定二叉搜索树（BST）的根节点+root+和要插入树中的值+value+，将值插入到二叉搜索树中。+返回插入后二叉搜索树的根节点。
二叉搜索树的插入删除修剪
Leetcode701-二叉搜索树中的插入操作
- 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
- 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
- 输入：root = [4,2,7,1,3], val = 5
- 输出：[4,2,7,1,3,5]
public TreeNode insertIntoBST(TreeNode root, int val) {
return insert(root,val);
}
public TreeNode insert(TreeNode root,int val){
if(root==null){
return new TreeNode(val);
}
if(root.val>val){
root.left=insert(root.left,val);
}
if(root.val<val){
root.right=insert(root.right,val);
}
return root;
}
Leetcode450-删除二叉搜索树中的节点
- 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
- 输入：root = [5,3,6,2,4,null,7], key = 3
- 输出：[5,4,6,2,null,null,7]
public TreeNode deleteNode(TreeNode root, int key) {
root=delete(root, key);
return root;
}
private TreeNode delete(TreeNode root, int key) {
if(root==null){
return null;
}
if(root.val>key){
root.left=delete(root.left,key);
}
else if(root.val<key){
root.right=delete(root.right,key);
}
else{
if(root.left==null){
return root.right;
}
if(root.right==null){
return root.left;
}
TreeNode temp=root.right;
while(temp.left!=null){
temp=temp.left;
}
root.val=temp.val;
root.right=delete(root.right,temp.val);
}
return root;
}
Leetcode669-修剪二叉搜索树
- 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案
- 输入：root = [1,0,2], low = 1, high = 2
- 输出：[1,null,2]
public TreeNode trimBST(TreeNode root, int low, int high) {
return trim(root,low,high);
}
public TreeNode trim(TreeNode root,int low,int high){
if(root==null){
return null;
}
if(root.val<low){
return trim(root.right,low,high);
}
if(root.val>high){
return trim(root.left,low,high);
}
root.left=trim(root.left,low,high);
root.right=trim(root.right,low,high);
return root;
}