LeetCode 450 [Delete Node in a BST]

题目链接

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

题目描述

给定一颗二叉排序树的根结点以及一个值，要求删除二叉排序树中包含该值的结点，同时返回该树的最新的根结点。一般来说，删除可以通过两个步骤来完成，一是查找该结点，二是删除该结点（如果存在的话）。时间复杂度必须是O(h)，h表示树的高度。

解题思路

题目默认条件：若非特殊说明，二叉排序树不存在两个或多个结点包含同个值的情况。
查找“待删除结点”的步骤：
1. 从根结点开始查找，将当前结点的值与给定的值进行比较。
2. 如果当前结点的值比较大，则将当前结点的左结点设置为新的当前结点；如果当前结点的值比较小，则将当前结点的右结点设置为新的当前结点；如果值相等，则说明当前结点即为目标，结束查找过程。
3. 若当前结点为NULL，也结束查找过程。
4. 查找过程需要记录“待删除结点”的父结点，同时还要记录它是父结点的左孩子还是右孩子（下文使用“方向”来表示这个信息）。
删除“待删除结点”的步骤：
1. 若第一步查找不到“待删除结点”，则不需要执行删除操作，返回当前的根结点即可。
2. 若找到了要“待删除结点”，则需要分以下几种情况考虑：
  1. 情况1：“待删除结点”没有任何子结点。
    1. 如果“待删除结点”是根结点（即它的父结点为NULL），那么释放该结点，返回NULL，结束删除过程。
    2. 如果“待删除结点”不是根结点，那么释放该结点，同时将它的父结点的对应方向的子结点置为NULL，结束删除过程。
  2. 情况2：“待删除结点”只有左子结点。
    1. 如果“待删除结点”是根结点（即它的父结点为NULL），那么释放该结点，返回它的左子结点，结束删除过程。
    2. 如果“待删除结点”不是根结点，那么释放该结点，同时将它的父结点的对应方向的子结点置为它的左结点，结束删除过程。
  3. 情况3：待删除的结点只有右子结点（与情况2非常类似）。
    1. 如果“待删除结点”是根结点（即它的父结点为NULL），那么释放该结点，返回它的右子结点，结束删除过程。
    2. 如果“待删除结点”不是根结点，那么释放该结点，同时将它的父结点的对应方向的子结点置为它的右结点，结束删除过程。
  4. 情况4：“待删除结点”同时包含左右子结点。
    1. 这种情况下，我们的目标是找一个最合适的结点（下文使用“待交换结点”来表示它）来取代“待删除结点”的位置。二叉排序树的特性就是每一个结点都比它左子树的所有结点大，同时比它右子树的所有结点小。因此“待交换结点”要么是左子树中值最大的结点，要么是右子树中值最小的结点。后续描述使用右子树中值最小的结点作为“待交换结点”，左子树中值最大的结点理论上满足题目要求，但我未实际测试。
    2. 查找“待交换结点”的步骤：
      1. 从“待删除结点”的右子结点开始，查找以它为根的子树中值最小的结点，查找过程同样需要记录当前结点的父结点及方向。
      2. 二叉排序树中值最小的结点必定位于最左侧，因此只要当前结点存在左子结点，则持续将左子结点置为新的当前结点即可。
      3. 最后一个不包含左子结点的当前结点，就是“待交换结点”。
    3. “待交换结点”是必定存在的，既然找到了，就可以开始删除步骤了。题目并未要求实际删除该结点，因此通过变更该结点的值也可以实现类似功能。这里要做的，只是简单地把“待交换结点”的值赋给“待删除结点”。
    4. 最后要处理“待交换结点”，上文只说了它不包含左子结点，因此要考虑它是否存在右结点。如果它存在右结点，那么它的父结点的对应方向的子结点就是它的右结点，否则它的父结点的对应方向的子结点就是NULL。最后把“待交换结点”释放了即可。

C++代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* node2Del = root;
        TreeNode* parentOfNode2Del = NULL;
        int direction = 0;
        // find the node 2 delete and its parent
        while (node2Del) {
            if (node2Del->val == key) {
                break;
            } else if (node2Del->val > key) {
                parentOfNode2Del = node2Del;
                node2Del = node2Del->left;
                direction = -1;
            } else {
                parentOfNode2Del = node2Del;
                node2Del = node2Del->right;
                direction = 1;
            }
        }
        // node to delete not found, do nothng and return root
        if (!node2Del) {
            return root;
        }
        
        if (!node2Del->left && !node2Del->right) {  // node to delete has no child
            // node to delete is root
            if (!parentOfNode2Del) {
                delete root;
                return NULL;
            }
            // node to delete is not root
            delete node2Del;
            if (direction < 0) {
                parentOfNode2Del->left = NULL;
            } else {
                parentOfNode2Del->right = NULL;
            }
        } else if (node2Del->left && !node2Del->right) {    // node to delete has only left child
            // node to delete is root
            if (!parentOfNode2Del) {
                delete root;
                return root->left;
            }
            // node to delete is not root
            if (direction < 0) {
                parentOfNode2Del->left = node2Del->left;
            } else {
                parentOfNode2Del->right = node2Del->left;
            }
            delete node2Del;
        } else if (node2Del->right && !node2Del->left) {    // node to delete has only right child
            // node to delete is root
            if (!parentOfNode2Del) {
                delete root;
                return root->right;
            }
            // node to delete is not root
            if (direction < 0) {
                parentOfNode2Del->left = node2Del->right;
            } else {
                parentOfNode2Del->right = node2Del->right;
            }
            delete node2Del;
        } else {    // node to delete has both left and right child
            // find the least value of right sub tree
            TreeNode* node2Switch = node2Del->right;
            TreeNode* parentOfNode2Switch = node2Del;
            int directionSwitch = 1;
            while (node2Switch->left) {
                parentOfNode2Switch = node2Switch;
                node2Switch = node2Switch->left;
                directionSwitch = -1;
            }
            // switch value
            node2Del->val = node2Switch->val;
            if (directionSwitch < 0) {
                parentOfNode2Switch->left = node2Switch->right;
            } else {
                parentOfNode2Switch->right = node2Switch->right;
            }
            delete node2Switch;
        }
        
        return root;
    }
};

Menu

题目链接

题目描述

解题思路

C++代码