Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove. If the node is found, delete the node. Note: Time complexity should be O(height of tree).
Example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
root = [5,3,6,2,4,null,7] key = 3 5 / 3 6 / 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / 4 6 / 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / 2 6 4 7
解题思路
二分遍历BST,发现对应的节点root,查找右子树最小的元素current,将root.left接到current.left上,返回root.right
Go代码实现
Go代码实现1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
func (root *TreeNode, key int ) *TreeNode { if root == nil { return root } root = findDelete(root, key) return root } func findDelete (root *TreeNode, key int ) *TreeNode { if root == nil { return root } if root.Val == key{ if root.Left == nil { return root.Right }else if root.Right == nil { return root.Left } current := root.Right for current.Left != nil { current = current.Left } current.Left = root.Left return root.Right }else if root.Val>key { root.Left = findDelete(root.Left, key) }else { root.Right = findDelete(root.Right, key) } return root }
Runtime: 1162 ms 27.78%
参考
近期评论