450_delete_node_in_a_bst

450. 删除二叉搜索树中的节点 中等

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

    5
   / \
  4   6
 /     \
2       7

另一个正确答案是 [5,2,6,null,4,null,7]。

    5
   / \
  2   6
   \   \
    4   7

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 5}
    root.Left = &TreeNode{Val: 3}
    root.Left.Left = &TreeNode{Val: 2}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right = &TreeNode{Val: 6}
    root.Right.Right = &TreeNode{Val: 7}
    debug(deleteNode(root, 5)) // 2 3 4 6 7  // ok
}

func debug(root *TreeNode) {
    if root == nil {
        return
    }
    debug(root.Left)
    fmt.Print(root.Val, " ")
    debug(root.Right)
}

func deleteNode(root *TreeNode, key int) *TreeNode {
    if root == nil {
        return nil
    }
    var parent, cur *TreeNode = nil, root

    // 查找
    for cur != nil && cur.Val != key {
        parent = cur
        if cur.Val > key {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }

    switch {
    case cur == nil: // 没找到
        return root
    case parent == nil: // 需要去掉根节点，则将左子树嫁接到右子树上
        return insertNode(root.Right, root.Left)
    case cur.Val < parent.Val:
        parent.Left = nil
    case cur.Val > parent.Val:
        parent.Right = nil
    }

    // 将左子树和右子树转移到父节点上
    if cur.Left != nil {
        insertNode(root, cur.Left)
    }
    if cur.Right != nil {
        insertNode(root, cur.Right)
    }
    return root
}

func insertNode(root, subNode *TreeNode) *TreeNode {
    if root == nil {
        return subNode
    }
    if subNode == nil {
        return root
    }
    var parent, cur *TreeNode = nil, root
    for cur != nil {
        parent = cur
        if cur.Val > subNode.Val {
            cur = cur.Left
        } else {
            cur = cur.Right
        }
    }

    if parent.Val < subNode.Val {
        parent.Right = subNode
    } else {
        parent.Left = subNode
    }
    return root
}