450. Delete Node in a BST

450. Delete Node in a BST

题目描述

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).

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
Example:
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

题目大意

删除二叉树节点

解题思路

遍历二叉树,找到目标节点。
如果目标节点左子树或右子树为nil,则将目标节点与其替换。
如果目标节点左右子树都不为nil,则将左子树与目标节点替换,为使二叉树在删除节点后,仍然保留二叉树特性。需以左子树为key,重复以上操作。

代码

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
36
37
38
/**
* Definition for a binary tree node.
* public class TreeNode {
* public var val: Int
* public var left: TreeNode?
* public var right: TreeNode?
* public init(_ val: Int) {
* self.val = val
* self.left = nil
* self.right = nil
* }
* }
*/
class Solution {
func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
guard let tree = root else { return root }
if tree.val > key {
tree.left = deleteNode(tree.left, key)
}
else if tree.val < key {
tree.right = deleteNode(tree.right, key)
}
else {
if tree.left == nil {
return tree.right
}else if tree.right == nil {
return tree.left
}
var node = tree.left
while node?.right != nil {
node = node?.right
}
tree.val = node!.val
tree.left = deleteNode(tree.left, tree.val)
}
return tree
}
}
0%