leetcode 450 Delete Node in a BST
z
 2019-06-08 17:51:25  

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:

  1. Search for a node to remove.
  2. 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

在一颗二叉搜索树中，去掉指定的数，构建新的二叉搜索树。

  • 我们假设deleteNode函数返回已经修改的二叉搜索树的子树，我们递归的寻找需要删除的那个root
  • 当我们找到了这个root之后，判断这个root是否只有一个左子树或者右子树，这种情况下，只要把当前的root替换为其左子树的root或者右子树的root即可
  • 如果我们要delete的这个root有左右子树都有
    • 那么我么去他的左子树，找到他左子树的最大的数，令root的值等于该最大值，并且在其root的左子树中delete该最大值节点
    • 或者我们去他的右子树，找到他右子树的最小的数，令root的值等于该最小值，并且在其root的右子树中delete该最小节点
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def deleteNode(self, root, key):
        if not root:
            return root
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        else:
            if not root.left:
                return root.right
            if not root.right:
                return root.left
            t = root.left
            while t.right:
                t = t.right
            root.val = t.val
            root.left = self.deleteNode(root.left, t.val)
        return root