LeetCode 450. 删除二叉搜索树中的节点【非递归 & 直接修改指针不修改val】

爱被打了一巴掌 2022-10-22 07:32 21阅读 0赞

> 如果是的节点p叶子直接删除，  
> 如果不是叶子  
> 把右子树挂在左子树最右边孩子的右边  
> 或者把左子树挂在右子树最左边的孩子的左边  
> 然后用p父亲per，p可能是父亲per的左孩子或者有孩子重新指向p的两个孩子重新构造的那个子树即可  
> 把p删除掉

[https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/][https_leetcode-cn.com_problems_delete-node-in-a-bst_solution_shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l]

> 官方题解修改了节点的val值，但是操作简单  
> 题目中没有要求不能修改节点的值，所以也是一个合法的解  
> 但是比较好奇LeetCode是怎么判这种不仅一个答案的题目

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
    #define debug(x) cout<<#x<<": "<<(x)<<endl;
    
    class Solution { 
    public:
        TreeNode* deleteNode(TreeNode* root, int key) { 
            
            auto p = root;
            auto par = p;
            int lr = -1; // 0 l 1 r
            
            while(p!=nullptr){ 
                if( p->val == key ){ 
                    break;
                }else if(p->val < key){ 
                    par = p;
                    lr = 1;
                    p = p->right;
                }else{ 
                    par = p;
                    lr = 0;
                    p = p->left;
                }
            }
    
            if(p==nullptr){ 
                return root;
            }
            auto l = p->left;
            auto r = p->right;
            
            auto lrrt = l;
            if(l==nullptr && r == nullptr){ 
                ;
            }else if(l!=nullptr){ 
                
                while(l->right !=nullptr){ 
                    l = l->right;
                }
                l->right = r;
            }
            else if(r!=nullptr){ 
                lrrt = r;
                while(r->left !=nullptr){ 
                    r = r->left;
                }
                r->left = l;
            }
    
            if(lr == -1){ 
                root = lrrt;
            }
            else if(lr==0){ 
                par->left = lrrt;
            }
            else{ 
                par->right = lrrt;
            }
    
            return root;
        }
    };

![在这里插入图片描述][20210404215630318.png]

[https_leetcode-cn.com_problems_delete-node-in-a-bst_solution_shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l]: https://leetcode-cn.com/problems/delete-node-in-a-bst/solution/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian-by-l/
[20210404215630318.png]: /images/20221022/6643888446b14fd199717ff547884763.png