企业网站建设方案精英,丹棱网站建设,邢台seo外包,wordpress 图床 插件450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key#xff0c;删除二叉搜索树中的 key 对应的节点#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树#xff08;有可能被更新#xff09;的根节点的引用。
一般来说#xff0c;删除节点可…450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 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
输出: []
思路要是被删除的节点是叶子节点或者只有左孩子或右孩子那么处理起来很简单。要是需要被删除的节点既有左孩子又有右孩子就需要左进一步处理了。那么在找到需要删除的节点后需要把被删除节点的左子树接在被删除节点的右子树的最左叶子节点因此用一个节点遍历找到右子树的最左叶子节点接上左子树。接下来需要做的就是删除被删除节点了rootroot-right下面代码中的delete都是可以缺省的只是一个释放内存的操作。 代码实现
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(!root) return root;if(root-val key) {if(!root-left !root-right) {delete root;return nullptr;}else if(!root-left) {auto ret root-right;delete root;return ret;}else if(!root-right) {auto ret root-left;delete root;return ret;}else {TreeNode *node root-right;while(node-left) {node node-left;}node-left root-left;auto r root;root root-right;delete r;return root;}}if(root-val key) root-left deleteNode(root-left, key);if(root-val key) root-right deleteNode(root-right, key);return root;}
};
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
示例 1 输入root [1,0,2], low 1, high 2
输出[1,null,2]示例 2 输入root [3,0,4,null,2,null,null,1], low 1, high 3
输出[3,2,null,1]
思路也是递归调用首先是当走到空节点返回针对于该被修剪的节点在满足被剪条件后断开这个连接度连接到左孩子或右孩子即可具体看是大于范围-找左孩子小于范围-找右孩子。
代码实现
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root nullptr) return nullptr;if(root-val high) {TreeNode *left trimBST(root-left, low, high);return left;}if(root-val low) {TreeNode *right trimBST(root-right, low, high);return right;}root-left trimBST(root-left, low, high);root-right trimBST(root-right, low, high);return root;}
};
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1 输入nums [-10,-3,0,5,9]
输出[0,-3,9,-10,null,5]
解释[0,-10,5,null,-3,null,9] 也将被视为正确答案示例 2 输入nums [1,3]
输出[3,1]
解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
思路1迭代使用三个队列一个维护节点另外两个维护下标因为要建立高度平衡的二叉搜索树那么就需要leftmidright三个下标
代码实现1
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {queueTreeNode *que;queueintrightQue;queueintleftQue;TreeNode *root new TreeNode(0);que.push(root);leftQue.push(0);rightQue.push(nums.size() - 1);while(!que.empty()) {TreeNode *node que.front();que.pop();int left leftQue.front();leftQue.pop();int right rightQue.front();rightQue.pop();int mid left ((right - left)/2);node-val nums[mid];if(left mid - 1) {node-left new TreeNode(0);que.push(node-left);leftQue.push(left);rightQue.push(mid - 1);}if(right mid 1) {node-right new TreeNode(0);que.push(node-right);leftQue.push(mid 1);rightQue.push(right);}}return root;}
};
思路2递归通过递归调用不断创建和给父节点接上新节点完成二叉搜索树的构建很明显如果要高度平衡那么leftmidright三个下标是不可少的。
代码实现2
class Solution {
public:TreeNode* traversal(vectorint nums, int left, int right) {if(left right) return nullptr;int mid left ((right - left) / 2);TreeNode *root new TreeNode(nums[mid]);root-left traversal(nums, left, mid - 1);root-right traversal(nums, mid 1, right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {TreeNode *root traversal(nums, 0, nums.size() - 1);return root;}
};
