（js）leetcode 450. 删除二叉搜索树中的节点

╰+攻爆jí腚メ 2023-01-04 13:27 120阅读 0赞

### 题目： ###

> 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
> 
> 一般来说，删除节点可分为两个步骤：
> 
> 首先找到需要删除的节点；  
> 如果找到了，删除它。  
> 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。
> 
> 示例:
> 
> root = \[5,3,6,2,4,null,7\]  
> key = 3
> 
>     5  
>    / \\  
>   3   6  
>  / \\   \\  
> 2   4   7
> 
> 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
> 
> 一个正确的答案是 \[5,4,6,2,null,null,7\], 如下图所示。
> 
>     5  
>    / \\  
>   4   6  
>  /     \\  
> 2       7
> 
> 另一个正确答案是 \[5,2,6,null,4,null,7\]。
> 
>     5  
>    / \\  
>   2   6  
>    \\   \\  
>     4   7

### 思路： ###

> 1. 节点为空，返回null
> 
> 2. 如果目标节点没有子节点，则直接删除，如果有一个非空子节点，则让该子节点代替自己的位置
> 
> 3. 若目标节点有两个子节点，则需要找到左子树中最小的那个节点，或者右子树中最大的节点代替自己的位置（本题中使用的是第二种）

### 代码实现： ###

/**
     * Definition for a binary tree node.
     * function TreeNode(val, left, right) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.left = (left===undefined ? null : left)
     *     this.right = (right===undefined ? null : right)
     * }
     */
    /**
     * @param {TreeNode} root
     * @param {number} key
     * @return {TreeNode}
     */
    var deleteNode = function(root, key) {
        if(root == null) return null;
        if(root.val === key) {
            // 如果目标节点没有子节点，则直接删除，如果有一个非空子节点，则让该子节点代替自己的位置
            if(root.left === null) return root.right;
            if(root.right === null) return root.left;
    
            // 处理目标节点有两个子节点的情况
            let minNode = getMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode(root.right, minNode.val);
        } else if(root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if(root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    };
    
    var getMin = function(node) {
        // BST 最左边的就是最小的
        while(node.left !== null) node = node.left;
        return node;
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70]: /images/20221119/5cc35ad89b174550b032d6bc2d9001bf.png