450 - 删除二叉搜索树中的节点

题目链接

删除二叉搜索树中的节点

题目

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

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

思路

删除二叉树的节点有以下几种情况：

1. 删除的节点不存在，那么就不做任何操作，直接返回root。
2. 删除的节点是leaf，叶子节点直接删除。
3. 删除的节点单侧有子树，即存在左子树或者右子树。那么将parent指向该节点的指针指向node的successor。
4. 删除的节点有左子树和右子树。那么我们要找到右子树中最小的节点（右子树中最左侧的节点）来代替要删除的节点。用minNode来代表右子树中最小的节点。
   1. minNode不存在子树。那么直接将minNode的parent指针改变为null。
   2. minNode存在子树，那么只能是右子树，因为minNode是最左侧节点。那么将minNode的parent指针指向minNode的right。

解题方法

因为要删除节点，所以我们需要记录当前节点的父节点，定义两个变量node和parent。同时，在寻找minNode的时候也要定义一个minParent作为minNode的父节点，因为如果node存在左右子树，我们需要删除的是minNode节点，而不是node这个节点，对于node节点，我们只需要修改val。

代码

/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
  if(!root) {
    return null;
  }
  let node = root;
  let parent = null;
  // 查找要删除的node
  while(node) {
    if(node.val === key) {
      break;
    } else if(node.val < key) {
      parent = node;
      node = node.right;
    } else {
      parent = node;
      node = node.left;
    }
  }

  if(!node) {
    return root;
  }

  // 如果node是leaf
  if(!node.left && !node.right) {
    if(parent === null) {
      return null;
    } else if(node === parent.left) {
      parent.left = null;
    } else if(node === parent.right) {
      parent.right = null;
    }
  } else {
    // 如果node没有右节点，只有左节点
    if(!node.right || !node.left) {
      if(parent === null) {
        return root.left || root.right;
      }
      if(node === parent.left) {
        parent.left = node.right || node.left;
      } else {
        parent.right = node.right || node.left;
      }
    } else {
      // 左右节点都有
      // 那么找到右子树的最小节点（最左侧的节点）
      let minParent = node;
      let minNode = node.right;
      while(minNode.left) {
        minParent = minNode;
        minNode = minNode.left;
      }
      node.val = minNode.val;
      if(minParent === node) {
        node.right = minNode.right;
      } else {
        minParent.left = minNode.right;
      }
    }
  }

  return root;
};

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$