给定一个节点数目为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

输出

{}
加载中...