[数据结构与算法]java二叉树删除节点

二叉树的删除要考虑三种情况
1.删除的节点是叶子节点2.删除的节点只有一个子树3.删除的节点有两个子树

删除的节点是叶子节点
找到删除的叶子结点tNode
找到目标节点的父节点pNode（考虑是否有父节点）
找到删除节点是父节点的左子树还是右子树
根据前边情况进行删除
右子树：p.rc=null
左子树：p.lc=null

删除的节点只有一个子树
找到删除的叶子结点tNode
找到目标节点的父节点pNode（考虑是否有父节点）
找到删除节点是父节点的左子树还是右子树
确定删除节点是左子树还是右子树
根据前边情况进行删除
tNode是它父节点的左子树
tNode有左子树 ： pNode.lc=tNode.lc
tNode有右子树 ： pNode.lc=tNode.rc
tNode是是它父节点的右子树
tNode有左子树 ： pNode.rc=tNode.lc
tNode有右子树 ： pNode.rc=tNode.rc

删除的节点有两个子树
找到删除的叶子结点tNode
找到目标节点的父节点pNode（考虑是否有父节点）
找到删除节点右子树中最小的或找到左子树中最大的
将右子树当中最大的值替换掉删除节点的值
使删除叶子节点的逻辑，删除最小值

//找到要删除的节点
	public TreeNode searchDelnode(TreeNode node,Integer val) {
		if(node==null) {
			return null;
		}
		if(node.val==val) {
			return node;
		}else if(val>node.val){
			if(node.rightNode==null) {
				return null;
			}
			return searchDelnode(node.rightNode, val);
		}else {
			if(node.leftNode==null) {
				return null;
			}
			return searchDelnode(node.leftNode, val);
		}
	}

//找到要删除节点的父节点
	public TreeNode searchDelpartent(TreeNode node,Integer val) {
		if(node==null) {
			return null;
		}
		if((node.leftNode!=null&&node.leftNode.val==val)||(node.rightNode!=null&&node.rightNode.val==val)) {
			return node;
		}else {
			if(node.leftNode!=null&&val<node.val) {
				return searchDelpartent(node.leftNode, val);
			}else if(node.rightNode!=null&&val>node.val){
				return searchDelpartent(node.rightNode, val);
			}else {
				return null;
			}
		}
	}

//二叉树删除节点
	public void del(TreeNode node,Integer val) {
		if(node==null) {
			return;
		}
		//1.找到要删除的节点
		TreeNode targetNode=searchDelnode(node, val);
		//2.没有找到要删除的节点
		if(targetNode==null) {
			return;
		}
		//3.找到要删除节点的父节点
		TreeNode parentNode=searchDelpartent(node, val);
		if(node.rightNode==null&&node.leftNode==null) {
			root=null;
			return;
		}
		if(parentNode==null&&(targetNode.rightNode!=null||targetNode.leftNode!=null)) {
			int min=searchRightMin(targetNode.rightNode);
			targetNode.val=min;
			return;
		}
		if(targetNode.leftNode==null&&targetNode.rightNode==null) {
			if(parentNode.rightNode!=null&&parentNode.rightNode.val==targetNode.val) {
				parentNode.rightNode=null;
			}else if(parentNode.leftNode!=null&&parentNode.leftNode.val==val){
				parentNode.leftNode=null;
			}
		}else if(targetNode.leftNode!=null&&targetNode.rightNode!=null) {
//在删除节点由左右两个子树时，我们选择找删除节点右子树的最小值，我们可以写一个方法，在这个方法里不仅找到最小值，并把这个位置的元素进行删除
			int min=searchRightMin(targetNode.rightNode);
			targetNode.val=min;
		}else {
			if(targetNode.rightNode!=null) {
				if(parentNode.rightNode.val==targetNode.val) {
					parentNode.rightNode=targetNode.rightNode;
				}else {
					parentNode.leftNode=targetNode.rightNode;
				}
			}else{
				if(targetNode.rightNode.val==targetNode.val) {
					parentNode.rightNode=targetNode.leftNode;
				}else {
					parentNode.leftNode=targetNode.leftNode;
				}
			}
		}
	}