LeetCode 450.删除二叉搜索树的结点

1.题目：

给定一个二叉搜索树的根节点 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]。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/delete-node-in-a-bst 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.代码：

/**
 * 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){
            if(root.left==null && root.right!=null){//左为空，右不为空
                return root.right;
            }else if(root.right==null && root.left!=null){//左不空，右空
                return root.left;
            }else if(root.left==null && root.right==null){//左空，右空
                return null;
            }
            else {
                TreeNode cur = root.right;//左不空，右不空 定义指针指向结点的右孩子
                while(cur.left!=null ){//让指针遍历到最左边的孩子
                    cur = cur.left;
                }
                cur.left=root.left;//让要删除的的结点的左孩子拼接到指针的左孩子上
                root=root.right;//删除结点，就是让结点的右孩子直接覆盖左孩子
                return root;//最后返回该节点
            }
        }
        if(root.val>key) root.left= deleteNode(root.left,key);//左
        if(root.val<key) root.right =deleteNode(root.right,key);//右
        return root;
        

    }
}