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%