450. Delete Node in a BST

Loading...LeetCode

第一步肯定是利用BST的性质寻找node.val==key的节点，主要是找到后的剪接部分比较麻烦，可以有两种方式处理：

1. 直接剪接：将该节点的右子节点放在左子节点的最右边叶节点（左子树最大值）的右侧。这样，值仍然是有序的。实现比较简单，但会提高tree的高度。

2. recursive：在右子树中寻找最左叶节点（值最小）作为替代key的值，并且对右子树删除该值后接到右侧。或者，在左子树中寻找最右叶节点（值最大）作为替代key的值，并且对左子树删除该值后接到左侧。

Aug 30:

BST中，删除当前node并保持BST，需要找到比当前node刚好大一点/小一点（右子树找最小/左子树找最大）的node，这个操作还挺常见的，记忆一下。

recursive

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root: return
        
        # 找到key
        if root.val == key:
            # 没有子树，即不需要考虑剪接
            if not root.left and not root.right: 
                root = None
            # 有右子树 -> 需要找刚好比目前大一点的（右子树children中最小的）
            elif root.right:
                rightSmallest = root.right
                while rightSmallest.left:
                    rightSmallest = rightSmallest.left
                root.val = rightSmallest.val
                root.right = self.deleteNode(root.right, root.val)
            # 有左子树 -> 需要找刚好比目前小一点的（左子树children中最大的）
            else:
                leftLargest = root.left
                while leftLargest.right:
                    leftLargest = leftLargest.right
                root.val = leftLargest.val
                root.left = self.deleteNode(root.left, root.val)
            # 左右子树这两个存在判断可以调换顺序，只要至多执行其中一个，均会产生符合要求的解。
                
        # key比当前value小 -> key在左子树
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        
        # key比当前value大 -> key在右子树
        else:
            root.right = self.deleteNode(root.right, key)
            
        return root

直接剪接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        if not root: return
        
        # 找到key
        if root.val == key:
            # 把右子树剪接到左子树的最右叶节点右侧，结果仍然是BST
            if root.left:
                leftLargest = root.left
                while leftLargest.right:
                    leftLargest = leftLargest.right
                leftLargest.right = root.right
                root.right = None
                root = root.left
            # 没有左子树就直接接右子树上去
            else:
                root = root.right
                
        # key比当前value小 -> key在左子树
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        
        # key比当前value大 -> key在右子树
        else:
            root.right = self.deleteNode(root.right, key)
            
        return root