Cocolib

Appearance

On this page

删除二叉搜索树中的节点 ​

Question

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。
image-20230614142826422

思路 ​

删除的节点有以下5种情况：

  1. 没找到要删除的节点
  2. 要删的是叶子节点
  3. 左不空右为空
  4. 左不空右为空
  5. 左右都不为空（最复杂的情况）
js
var deleteNode = function(root, key) {
    if(root===null) return null     //没找到要删除的节点
    if(root.val===key){
        if(root.left===null&&root.right===null){    //要删的是叶子节点
            return null
        }else if(root.left!=null&&root.right===null){   //左不空右为空
            return root.left
        }else if(root.left===null&&root.right!=null){   //左不空右为空
            return root.right
        }else{                  //左右都不为空
            //找到右子树的最左边的节点
            let cur = root.right
            while(cur.left!=null)  cur = cur.left
            //将左子树作为节点的左子树
            cur.left = root.left
            return root.right
        }
    }
    if(root.val>key)    root.left = deleteNode( root.left,key)
    if(root.val<key)    root.right = deleteNode( root.right,key)
    return root
};