嵌入式开发前景,seo 能提高网站速度吗,dw网页设计与制作,平面设计在线课程1. 二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作https://leetcode.cn/problems/insert-into-a-binary-search-tree/给定二叉搜索树#xff08;BST#xff09;的根节点 root 和要插入树中的值 value #xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。…1. 二叉搜索树中的插入操作
701. 二叉搜索树中的插入操作https://leetcode.cn/problems/insert-into-a-binary-search-tree/给定二叉搜索树BST的根节点 root 和要插入树中的值 value 将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 新值和原始二叉搜索树中的任意节点值都不同。
注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1 输入root [4,2,7,1,3], val 5
输出[4,2,7,1,3,5]
解释另一个满足题目要求可以通过的树是示例 2
输入root [40,20,60,10,30,50,70], val 25
输出[40,20,60,10,30,50,70,null,null,25]
示例 3
输入root [4,2,7,1,3,null,null,null,null,null,null], val 5
输出[4,2,7,1,3,5]
解题思路
这道题只要求了满足二叉搜索树的特性所以只需要最后一路遍历到叶子节点就行了。
代码
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if (root null)return new TreeNode(val);TreeNode head root;TreeNode pre root;while (root ! null) {pre root;if (root.val val)root root.left;elseroot root.right;}if (pre.val val)pre.left new TreeNode(val);elsepre.right new TreeNode(val);return head;}
}
2. 删除二叉搜索树中的节点
450. 删除二叉搜索树中的节点https://leetcode.cn/problems/delete-node-in-a-bst/
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。
一般来说删除节点可分为两个步骤
首先找到需要删除的节点如果找到了删除它。
示例 1: 输入root [5,3,6,2,4,null,7], key 3
输出[5,4,6,2,null,null,7]
解释给定需要删除的节点值是 3所以我们首先找到 3 这个节点然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2: 输入: root [5,3,6,2,4,null,7], key 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点示例 3:
输入: root [], key 0
输出: [] 解题思路
删除比较复杂但是还好不是红黑树不会存在翻转这些操作。
删除操作有几种情况需要进行列举
为null不做操作没有左右子树删除节点就行只有左子树删除节点左子树替换位置只有右子树删除节点右子树替换位置左右子树都有二叉搜索树的特性是左子树一定比右子树小所以可以把左子树整体反倒右子树的最左叶子的左侧。
使用递归实现
返回值和参数root和key返回迭代后的子树root终结条件当root为null的时候返回null递归逻辑不为key的时候判断大小然后走左或者右子树进行递归为key的时候执行五个判断逻辑。
代码
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;else if (root.right null)return root.left;else {TreeNode cur root.right;while (cur.left ! null) {cur cur.left;}cur.left root.left;return root.right;}}if (root.val key) {root.left deleteNode(root.left, key);}if (root.val key) {root.right deleteNode(root.right, key);}return root;}
}
