二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
迭代
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {TreeNode node=new TreeNode(val);if(root==null) return node;TreeNode cur=root;while(true){if(cur.val>val){if(cur.left==null){cur.left=node;break;}cur=cur.left;}if(cur.val<val){if(cur.right==null){cur.right=node;break;}cur=cur.right;}}
return root;}
}递归
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root==null) return new TreeNode(val);if(root.val>val)root.left=insertIntoBST(root.left,val);elseroot.right=insertIntoBST(root.right,val);return root;}
}删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点 - 力扣（LeetCode）
class Solution {public 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 cur=root.left;while(cur.right!=null) cur=cur.right;//这一步利用二叉搜索树的性质是找到左子树的最大值cur.right=root.right;return root.left;} else if(root.val>key) root.left=deleteNode(root.left,key);else root.right=deleteNode(root.right,key);return root;}}修建二叉搜索树
669. 修剪二叉搜索树 - 力扣（LeetCode）
递归
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) return null;if(root.val<low) return trimBST(root.right,low,high);else if(root.val>high) return trimBST(root.left,low,high);root.left=trimBST(root.left,low,high);root.right=trimBST(root.right,low,high);return root;}
}迭代
这个思路其实分别处理左子树，右子树，然后处理的逻辑和删除二叉搜索树的节点相似
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {while(root!=null&&(root.val>high||root.val<low)) root=root.val>high?root.left:root.right;TreeNode t=root;while(root!=null){while(root.left!=null&&root.left.val<low) root.left=root.left.right;root=root.left;}root=t;while(root!=null){while(root.right!=null&&root.right.val>high) root.right=root.right.left;root=root.right;}return t;}}将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
构造平衡树-所以用数组中间的值作为根节点，左侧的值作为左子树，右侧的值作为右子树
class Solution {public TreeNode sortedArrayToBST(int[] nums) {return dfs(nums,0,nums.length-1);}public TreeNode dfs(int[] nums,int l,int h){if(l>h){return null;}int m=l+(h-l)/2;TreeNode root=new TreeNode(nums[m]);root.left=dfs(nums,l,m-1);root.right=dfs(nums,m+1,h);return root;}
}将二叉树搜索树转换成累加树
538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
class Solution {int tot=0;public TreeNode convertBST(TreeNode root) {dfs(root);return root;}public void dfs(TreeNode root){if(root==null) return ;dfs(root.right);tot+=root.val;root.val=tot;dfs(root.left);}
}二叉树终于完了，要去复盘啦，耗时一周+一天