删除二叉搜索树中的节点，力扣405题

本文主要是介绍删除二叉搜索树中的节点，力扣405题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

//    首先要清楚的是deleteNode这个函数起到了什么作用，返回的是什么，心里面清楚这个才能写后续的递归函数。
//    本题中，deleteNode函数是接收一个根节点和一个值，删除这棵树中和该值相等的那个结点。返回删除后的树的根节点。
//    然后，我们就可以根据这个函数去编写递归。
//    首先，要进行分类讨论：
//    1.左右孩子都为空：直接返回空结点作为删除后的树。
//    2.左孩子为空，右孩子不为空，直接删除根结点，返回右孩子结点作为删除之后的树。
//    3.右孩子为空，左孩子不为空，直接删除根节点，返回左孩子结点作为删除之后的树。
//    4.最后一种情况就是左孩子不为空，右孩子也不为空。这种情况下，按照二叉搜索树的删除的官方做法，是找到它的前驱节点（左子树中最右边的结点），或者是找到它的后继结点（右子树中的最左边的结点）。将它作为根节点，然后原来的左子树作为新的左子树，原来的右子树作为新的右子树。
//      同时，网上还有另外一种做法，就是将左子树整个的挂在右子树的最左边的结点的左孩子下，返回右子树的根作为新的根节点，这样也可以，但是这样好像会不断地增加树地高度，最终这个树会变成一个链表。

下面是官方做法。

//    首先要清楚的是deleteNode这个函数起到了什么作用，返回的是什么，心里面清楚这个才能写后续的递归函数。
//    本题中，deleteNode函数是接收一个根节点和一个值，删除这棵树中和该值相等的那个结点。返回删除后的树的根节点。
//    然后，我们就可以根据这个函数去编写递归。
//    首先，要进行分类讨论：
//    1.左右孩子都为空：直接返回空结点作为删除后的树。
//    2.左孩子为空，右孩子不为空，直接删除根结点，返回右孩子结点作为删除之后的树。
//    3.右孩子为空，左孩子不为空，直接删除根节点，返回左孩子结点作为删除之后的树。
//    4.最后一种情况就是左孩子不为空，右孩子也不为空。这种情况下，按照二叉搜索树的删除的官方做法，是找到它的前驱节点（左子树中最右边的结点），或者是找到它的后继结点（右子树中的最左边的结点）。将它作为根节点，然后原来的左子树作为新的左子树，原来的右子树作为新的右子树。
//      同时，网上还有另外一种做法，就是将左子树整个的挂在右子树的最左边的结点的左孩子下，返回右子树的根作为新的根节点，这样也可以，但是这样好像会不断地增加树地高度，最终这个树会变成一个链表。public TreeNode deleteNode(TreeNode root, int key) {if(root==null){return null;}if(root.val==key){//中if(root.left==null && root.right==null){return null;}else if(root.left==null && root.right!=null){return root.right;}else if(root.right==null && root.left!=null){return root.left;}else{TreeNode newRoot=root.right;//用于寻找右子树中的最左下角的节点while(newRoot.left!=null){newRoot=newRoot.left;}root=deleteNode(root,newRoot.val);//因为newRoot节点要作为新的根节点，所以要在原来的树上递归删除它。newRoot.left=root.left;newRoot.right=root.right;root=newRoot;//设置为新的节点。}}else if(root.val>key){root.left=deleteNode(root.left,key);//左}else if(root.val<key){root.right=deleteNode(root.right,key);//右}return root;}

这篇关于删除二叉搜索树中的节点，力扣405题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---