A golang solution


  • 0
    N
    func searchNode(parent *TreeNode, child *TreeNode, key int) (p *TreeNode, c *TreeNode) {
        if child == nil || child.Val == key {
            return parent, child
        } else if child.Val < key {
            return searchNode(child, child.Right, key)
        } else {
            return searchNode(child, child.Left, key)
        }
    }
    
    func deleteNode(root *TreeNode, key int) *TreeNode {
        parent, child := searchNode(nil, root, key)
        if child == nil {
            return root
        }
        
        switch {
            case child.Left == nil && child.Right == nil:
                if parent == nil {
                    return nil
                } else {
                    if parent.Left == child {
                        parent.Left = nil
                    } else {
                        parent.Right = nil
                    }
                    return root
                }
            case child.Left == nil && child.Right != nil:
                if parent == nil {
                    return child.Right
                } else {
                    if parent.Left == child {
                        parent.Left = child.Right
                    } else {
                        parent.Right = child.Right
                    }
                    return root
                }
            case child.Left != nil && child.Right == nil:
                if parent == nil {
                    return child.Left
                } else {
                    if parent.Left == child {
                        parent.Left = child.Left
                    } else {
                        parent.Right = child.Left
                    }
                    return root
                }
            default:
                var node *TreeNode
                for node = child.Right; node.Left != nil; node = node.Left {
                }
                node.Left = child.Left
                if parent == nil {
                    return child.Right
                } else {
                    if parent.Left == child {
                        parent.Left = child.Right
                    } else {
                        parent.Right = child.Right
                    }
                    return root
                }
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.