LeetCode 450 Delete Node in a BST

概述

https://leetcode.com/problems/delete-node-in-a-bst/

删除一个节点，我们首先需要找到目标节点，然后用一个节点去替代其位置（或者重新整理 BST）。

1. 如果用其右子节点替代其位置，这样我们就需要处理其左子节点和右子节点的左子节点之间的冲突关系。
2. 如果用一个叶节点替代其位置，我们就不需要处理冲突关系了。

迭代法

1. 首先根据 BST 的性质定位到目标节点，
2. 之后用其右子树里的最小值来代替它，那我们就需要找到最小值，并删去它。
3. 如果其右子树为空，则更新其父节点对应的指针？不，这样太麻烦，直接用其取代其左子节点即可，即用其值和左右子节点。
4. 如果其左子树为空，则需要更新其父节点对应的指针。

好麻烦啊，肯定有简单的做法。

我们想一下，目标节点无非三种 case：

1. 根节点，中间节点，
   1. 如果其只有一个子节点，则父节点把对应指针指向该子节点即可；
   2. 如果其子节点双全，晋升其左子树，然后把右子树挂载到其左子树上；
2. 叶节点：需要父节点删除对应指针；

为了编程方便，我们需要为根节点构造一个 dummy 父节点。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode dummy(0, root, nullptr);
        auto p = &dummy;
        auto c = root;
        bool isLeft = true;  // does c is the left child of p?
        while (c && c->val != key) {
            if (c->val < key) {
                p = c;
                c = c->right;
                isLeft = false;
            } else {
                p = c;
                c = c->left;
                isLeft = true;
            }
        }
        
        if (!c) return root;  // not found
        if (c->left && c->right) {
            if (isLeft) {
                p->left = c->left;
            } else {
                p->right = c->left;
            }
            auto t = c->left;
            while (t->right) {
                t = t->right;
            }
            t->right = c->right;  // mount the origin right sub tree to the left tree
        } else if (c->left) {
            if (isLeft) {
                p->left = c->left;
            } else {
                p->right = c->left;
            }
        }  else if (c->right) {
            if (isLeft) {
                p->left = c->right;
            } else {
                p->right = c->right;
            }
        } else {  // all childred are nullptr
            if (isLeft) {
                p->left = nullptr;
            } else {
                p->right = nullptr;
            }
        }
        return dummy.left;
    }
};

递归法

实际上每次递归函数返回处理好后的子树的根节点就好，我们根本不用关心究竟是挂载在左边还是右边。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val == key) {
            if (root->left && root->right) {
                auto right = root->right;
                root = root->left;
                auto c = root;
                while (c->right) {
                    c = c->right;
                }
                c->right = right;
            } else if (root->left) {
                return root->left;
            } else if (root->right) {
                return root->right;
            } else {
                return nullptr;
            }
        } else if (root->val < key) {
            root->right = deleteNode(root->right, key);
        } else {
            root->left = deleteNode(root->left, key);
        }
        return root;
    }
};

Links: leetcode-450-delete-node-in-a-bst

未经允许，禁止转载，本文源站链接：https://iamazing.cn/