删除一个二叉搜索树中的节点_牛客题霸

给定一个节点数目为N的二叉搜索树的根节点root和一个值key，请你完成删除一个节点的功能 1.如果二叉搜索树有节点里面存在有该值的key，那么删除该节点，然后调整该树，使其还是一颗二叉搜索树，返回这颗新树的根节点 2.如果不存在有节点的值等于key，则不删除，直接返回原树的根节点 3.root里面的节点值各不相同 4.该题返回的二叉搜索树不唯一，你返回合法的一颗即可 5.该题有O(H)的时间复杂度的算法，H为树的高度，一种方法如下: 5.1如果key大于当前节点值，则去当前节点的右子树中删除； 5.2如果key小于当前节点值，则去当前节点的左子树中删除； 5.3如果key就是当前节点值，分为以下三种情况： 5.3.1当前节点只无左子树：删除了该节点，其右子树顶替其位置； 5.3.2当前节点只无右子树：删除了该节点，其左子树顶替其位置； 5.3.3其左右子树都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。 5.3.4其左右子树都无：直接删除该节点即可数据范围:

示例1

输入

{4,2,7,1,3,#,8},2

输出

{4,3,7,1,#,#,8}

说明


删除节点2，变为：
当然，如下二叉搜索树也视为正确解法之一:

示例2

输入

{4,2,7,1,3,#,8},5

输出

{4,2,7,1,3,#,8}

说明

没有值为5的节点，不删除，返回原树

示例3

输入

{},2

输出

{}