【lintcode】删除二叉查找树的节点

Bertha 。 2022-05-20 07:58 221阅读 0赞

描述
    给定一棵具有不同节点值的二叉查找树，删除树中与给定值相同的节点。
    如果树中没有相同值的节点，就不做任何处理。你应该保证处理之后的树仍是二叉查找树。 
    
    样例
    给出如下二叉查找树：
    
              5
    
           /    \
    
        3          6
    
     /    \
    
    2       4
    
    删除节点3之后，你可以返回：
    
              5
    
           /    \
    
        2          6
    
          \
    
             4
    
    或者：
    
              5
    
           /    \
    
        4          6
    
     /   
    
    2

题解（参考《算法导论》二叉搜索树部分）

/**
     * Definition of TreeNode:
     * class TreeNode {
     * public:
     *     int val;
     *     TreeNode *left, *right;
     *     TreeNode(int val) {
     *         this->val = val;
     *         this->left = this->right = NULL;
     *     }
     * }
     */
    
    
    class Solution {
    public:
        /*
         * @param root: The root of the binary search tree.
         * @param value: Remove the node with given value.
         * @return: The root of the binary search tree after removal.
         */
        TreeNode * removeNode(TreeNode * root, int value) {
            // write your code here
            if(root == NULL) 
                return root;
    
            //设置一个header结点作为root的父节点，便于解决root结点被删除的情况
            TreeNode *header = new TreeNode;
            header->left = root;
    
            //pair中记录搜索到的结点p和它的父节点pre
            pair<TreeNode*, TreeNode*> pair = my_search(root, value);
            //如果没有找到value，直接返回
            if(pair.first == NULL)
                return header->left;
            //删除结点
            my_delete(header, pair.second, pair.first);
            return header->left;
        }
    
        //搜索结点及其父节点，若没找到则返回pair(NULL, NULL)
        pair<TreeNode*, TreeNode*> my_search(TreeNode * root, int val) {
            TreeNode *p = root, *pre = root;
            while(p){
                if(p->val == val)
                    return pair<TreeNode*, TreeNode*>(p, pre);
    
                pre = p;
                if(val < p->val)
                    p = p->left;
                else
                    p = p->right;
            }
            return pair<TreeNode*, TreeNode*>(NULL, NULL);
        }
    
        //删除结点，注意这里传入了header结点，便于解决root被删除的情况
        void my_delete(TreeNode *header, TreeNode *&pre, TreeNode *&p) {
            if(pre == p){
                //若被删除的是root，则设置p的父结点pre为header
                pre = header;
            }
            //若左子树为空，则用p的右子树替换p
            if(p->left == NULL){
                my_move(pre, p, p->right);
                delete p;
                p = NULL;
            }
            //若右子树为空，则用p的左子树替换p
            else if(p->right == NULL){
                my_move(pre, p, p->left);
                delete p;
                p = NULL;
            }
            //若p的左右子树都不为空，则用p的右子树中最小的结点替换p
            else{
                pair<TreeNode*, TreeNode*> pair_t = minimum(p->right);
                TreeNode *t = pair_t.first, *pre_t = pair_t.second;
                //若t为p的右子结点，直接替换
                if(t == p->right){
                    t->left = p->left;
                    my_move(pre, p, t);
                    delete p;
                    p = NULL;
                }
                //否则
                else{
                    //先用t的右子结点替换t
                    my_move(pre_t, t, t->right);
                    //用t替换p
                    t->left = p->left;
                    t->right = p->right;
                    my_move(pre, p, t);
    
                    delete p;
                    p = NULL;
                }
            }
        }
    
        //该函数用于移动结点p2到p1的位置，pre为p1的父结点
        void my_move(TreeNode *pre, TreeNode *p1, TreeNode *p2) {
            if(p1 == pre->left)
                pre->left = p2;
            else
                pre->right = p2;
        }
    
        //寻找以root为根的BST的最小结点及其父结点
        pair<TreeNode*, TreeNode*> minimum(TreeNode *root) {
            TreeNode *p = root, *pre = root;
            if(!p) return pair<TreeNode*, TreeNode*>(p, pre);
            while(p->left){
                pre = p;
                p = p->left;
            }
            return pair<TreeNode*, TreeNode*>(p, pre);
        }
    };