江西中耀建设集团有限公司网站,网站开发下载哪个,网络安全防护软件,网站建设公司 佛山给定一个二叉搜索树的根节点 root 和一个值 key#xff0c;删除二叉搜索树中的 key 对应的节点#xff0c;并保证二叉搜索树的性质不变。返回二叉搜索树#xff08;有可能被更新#xff09;的根节点的引用。
一般来说#xff0c;删除节点可分为两个步骤#xff1a;
首先…给定一个二叉搜索树的根节点 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
输出: [] 提示:
节点数的范围 [0, 104].-105 Node.val 105节点值唯一root 是合法的二叉搜索树-105 key 105
class Solution {
public:TreeNode* dfs(TreeNode* root,int key){//第一种if(!root) return nullptr;if(root-val key){//第二种if(!root-left !root-right) return nullptr;//3else if(!root-left root-right){return root-right;}else if(root-left !root-right){return root-left;}else{//让右子树继承左子树继承到右子树得最左子树TreeNode* cur root-right;//处理目标结点左子树残骸while(cur-left){cur cur-left;}cur-left root-left;return root-right;}}if(root-val key){root-left dfs(root-left,key);}if(root-val key){root-right dfs(root-right,key);}return root;}TreeNode* deleteNode(TreeNode* root, int key) {return dfs(root,key);}
};
