[Vssue]0450.删除二叉搜索树中的节点.md

[youngyangyang04]

https://www.programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html

[Du1in9]

class Solution {
    public TreeNode deleteNode(TreeNode node, int val) {
        if (node == null) return null;
        if (val < node.val) {
            node.left = deleteNode(node.left, val);
        } else if (val > node.val) {
            node.right = deleteNode(node.right, val);
        } else {
            if (node.left == null) {            // 1. 左孩子为空
                return node.right;
            } else if (node.right == null) {    // 2. 右孩子为空
                return node.left;              
            } else {                            // 3. 左右孩子都不为空
                TreeNode next = node.right;     
                while (next.left != null) {     // 找到右子树的最小节点 8
                    next = next.left;
                }
                next.left = node.left;          // 将 5 放到 8 的左孩子上
                return node.right;              // 9 覆盖 7
            }
        }
        return node;
    }
}

[Kai-Bo]

/**

• 在二叉搜索树中删除节点 */ class BinaryTreeNo29 { public TreeNode deleteBST(TreeNode root, int val) { // 1 没有找到要删除的节点 if (root == null) return null; if (root.val > val) { root.right = deleteBST(root.right, val); } else if (root.val < val){ root.left = deleteBST(root.left, val); } else { // 2 找到了要删除的节点 // 2.1 如果左孩子为空，返回右孩子 if (root.left == null) return root.right; // 2.2 如果右孩子为空，返回左孩子 else if (root.right == null) return root.left; // 2.3 两个孩子都不为空 else { TreeNode node = root.right; while (node.left != null) node = node.left; node.left = root.left; return root.right; } } return root; } }

[lagrange10]

这个方案是教科书里面的交换节点，然后再次复用之前的程序逻辑，这样做把删除树中间的节点转化为简单的删除叶子节点，一个逻辑处理两种情况。

卡哥的方案1 会大大增加树的高度，仅做题正确。 方案2 会遍历整颗树，时间复杂度为$o(N)$, 因为没有利用二叉搜索树的性质。 以下方案个人分析为，先找到待删除节点$o(log N)$,然后交换节点再删除一次还是$o(log N)$, 因此整体时间复杂度为$o(log N)$

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        return helper(root, key);
    }

    TreeNode* helper(TreeNode* root, int key)
    {
        if(root == nullptr) return nullptr;
        // 1. 寻找要删除的节点 
        if(key > root->val) root->right = helper(root->right, key);
        else if (key < root->val) root->left = helper(root->left, key);
        // 2. 找到了进入删除操作，没找到就直接return root了。
        if(root->val == key)
        {
            TreeNode* temp = root;
            // 2.1 如果左右子树有一个为空，就直接拿另一个子树替代。
            // 这里包括了左右子树都空的情况。这是因为都空另一个子树也为空，拿另一个子树(nullptr)替代待删除的节点等价于删除。
            if(root->left == nullptr)
            {
                root = root->right;
            }
            else if(root->right == nullptr)
            {
                root = root->left;
            }
            // 2.2 是卡哥方法二提到的交换逻辑。
            else {
                TreeNode* cur = root->left;
                while(cur->right) {
                    cur = cur->right;
                }
                swap(root->val, cur->val);
                // 把待删除节点交换到左子树的最右节点以后
                // 问题转化为在左子树中删除key。而这种情况key在叶子节点，之前的程序可以处理。
                root->left = helper(root->left, key);
                return root;
            }
            delete temp;
        }

        return root;
    }
};

[MayaSHM]

这是利用寻找后继结点来删除值的python代码。假设要删除的是结点A，思路是先找到结点A的后继结点并进行值替换，然后在结点A的右子树中递归调用deleteNode函数删除后继结点，该方法不会改变树的高度

注：一个结点的后继结点是指将树中序遍历后，这个结点的下一个结点。例如中序遍历[1, 2, 3, 4, 5, 6, 7]，3的后继结点是4，是3的右子树中的最小值

楼下录友lagrange10的方法是寻找前驱节点，定义与后继结点相反

class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root:
            return None
        # 停止情况：到达要删除的结点
        if root.val == key:
            # 1. 无左右子结点——到达叶子结点，直接删除
            if not root.left and not root.right:
                return None
            # 2. 有左无右，则左子树上移
            elif root.left and not root.right:
                return root.left
            # 3. 无左有右，则右子树上移
            elif not root.left and root.right:
                return root.right
            # 4. 有左有右：
            #   4.1 找后继结点（中序遍历中，被删除结点的下一个）
            #   4.2 让后继结点的值替换被删除结点的值
            #   4.3 对后继结点本身再做一次删除操作
            else:
                # 找后继结点
                post_node = root.right  # 先来到右子树，随后一路向左
                while post_node.left:
                    post_node = post_node.left
                # 值替换
                root.val = post_node.val
                # 从当前结点的右子树开始，删除后继结点
                root.right = self.deleteNode(root.right, post_node.val)      
        else:
            # 继续搜索，并接住结构调整后的子结点
            if key < root.val:
                root.left = self.deleteNode(root.left, key) 
            else:
                root.right = self.deleteNode(root.right, key)
        return root