LeetCode_二叉搜索树_中等_450.删除二叉搜索树中的节点

一时失言乱红尘 2023-10-06 22:27 28阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并**保证二叉搜索树的性质不变**。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：  
① 首先找到需要删除的节点；  
② 如果找到了，删除它。

**示例 1：**

![在这里插入图片描述][ec533e7546e94c0c8a54c7a893c297fb.png]

输入：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\]。

![在这里插入图片描述][51fd85384c8a4b4e83b999e39a93d225.png]

**示例 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

**进阶：** 要求算法时间复杂度为 O(h)，h 为树的高度。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/delete-node-in-a-bst

## 2.思路 ##

（1）递归

## 3.代码实现（Java） ##

//思路1————递归
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public TreeNode deleteNode(TreeNode root, int key) {
        
            if (root == null) {
        
                return null;
            }
            if (root.val == key) {
        
                //要删除的节点就是当前根节点
                //1.处理左右子树为空的情况
                if (root.left == null) {
        
                    return root.right;
                }
                if (root.right == null) {
        
                    return root.left;
                }
                //2.处理左右子树均不为空的情况
                //获取右子树中值最小的节点
                TreeNode minNode = getMinNode(root.right);
                //删除右子树中值最小的节点
                root.right = deleteNode(root.right, minNode.val);
                //用右子树中值最小的节点替换当前根节点
                minNode.left = root.left;
                minNode.right = root.right;
                root = minNode;
            } else if (root.val > key) {
        
                //要删除的节点可能在当前根节点的左子树中
                root.left = deleteNode(root.left, key);
            } else {
        
                //要删除的节点可能在当前根节点的右子树中
                root.right = deleteNode(root.right, key);
            }
            return root;
        }
        
        //获取当前二叉搜索树中值最小的节点
        public TreeNode getMinNode(TreeNode node) {
        
            //二叉搜索树中最左边的节点即为值最小的节点
            while (node.left != null) {
        
                node = node.left;
            }
            return node;
        }
    }

[ec533e7546e94c0c8a54c7a893c297fb.png]: https://img-blog.csdnimg.cn/ec533e7546e94c0c8a54c7a893c297fb.png
[51fd85384c8a4b4e83b999e39a93d225.png]: https://img-blog.csdnimg.cn/51fd85384c8a4b4e83b999e39a93d225.png