您的位置:首页 > 教育 > 培训 > 随想录笔记-二叉树笔记

随想录笔记-二叉树笔记

2024/11/9 8:56:56 来源:https://blog.csdn.net/weixin_46321761/article/details/142298771  浏览:    关键词:随想录笔记-二叉树笔记

二叉搜索树中的插入操作

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);}
}

二叉树终于完了,要去复盘啦,耗时一周+一天

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com