题目链接:LeetCode 450. 删除二叉搜索树中的节点
题意:
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
1. 首先找到需要删除的节点;
2. 如果找到了,删除它。
解题思路:
对于待删除的节点,分为三种情况:
1. 情况一:待删除节点是叶子节点,直接删除该节点即可
2. 情况二:待删除节点只有一个孩子的情况,将它的左子树(或者右子树)直接覆盖待删除节点
3. 情况三:待删除节点左右孩子都有的情况,找到待删除结点的后继结点(从当前结点的右子树开始,一直往左走,直到走不下去为止),覆盖当前结点,删除后继结点,该后继节点一定是没有左子树的,因此删除后继节点就是情况二
代码:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil { //结点是空,直接返回
return nil
}
if root.Val == key{ //找到待删除结点
if root.Left == nil && root.Right == nil{ //待删除节点是叶子节点的情况
root = nil
}else if root.Right == nil { //只有左孩子的情况
root = root.Left
}else if root.Left == nil{ //只有右孩子的情况
root = root.Right
}else{ //左右孩子都有的情况
p := root.Right
for p.Left != nil { //寻找后继节点
p = p.Left
}
root.Val = p.Val
root.Right = deleteNode(root.Right,p.Val) //删除后继结点
}
return root
}
if key > root.Val{
root.Right = deleteNode(root.Right,key)
}else{
root.Left = deleteNode(root.Left,key)
}
return root
}