450.删除二叉搜索树中的节点
450.删除二叉搜索树中的节点
题解
如果key < root.Val，说明要删除的节点在BST的左子树，那么递归的去左子树删除即可
2 如果key > root.Val，说明要删除的节点在BST的右子树，那么递归的去右子树删除即可
3 如果key = root.Val，说明要删除的节点就是本节点，这一类又分以下三种情况:
要删除的节点是叶子节点，那很简单，直接将当前节点删除，置为nil即可;
要删除的节点有右子节点，那么为了维持BST的特性，我们需要找到该节点的后继节点post(BST中大于它的最小节点)，将该节点的值更新为后继节点post的值，然后递归的在当前节点的右子树中删除该后继节点post;
要删除的节点有左子节点，那么为了维持BST的特性，我们需要找到该节点的前驱节点pre(BST中小于于它的最大节点)，将该节点的值更新为前驱节点pre的值，然后递归的在当前节点的左子树中删除该前驱节点pre;
代码
type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func deleteNode(root *TreeNode, key int) *TreeNode { if root == nil { return root } if key < root.Val { root.Left = deleteNode(root.Left, key) } else if key > root.Val { root.Right = deleteNode(root.Right, key) } else { if root.Left == nil && root.Right == nil { root = nil } else if root.Right != nil { root.Val = successor(root).Val root.Right = deleteNode(root.Right, root.Val) } else if root.Left != nil { root.Val = predecessor(root).Val root.Left = deleteNode(root.Left, root.Val) } } return root } func predecessor(root *TreeNode) *TreeNode { pre := root.Left for pre.Right != nil { pre = pre.Right } return pre } func successor(root *TreeNode) *TreeNode { post := root.Right for post.Left != nil { post = post.Left } return post }
