二叉搜索树删除节点，递归和迭代：2 种方法求解《450. 删除二叉搜索树中的节点》

代码数据结构:树数据结构:二叉树数据结构:二叉搜索树算法:递归算法:迭代语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:TypeScript 语言:Java

2022-06-02 23:01:18

二叉搜索树删除节点图示，递归，迭代，2 方法求解《450. 删除二叉搜索树中的节点》

二叉搜索树删除节点图示

删除节点

二叉搜索树删除节点，如上图所示

例题

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

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

答案

递归

var deleteNode = function(root, key) {
  if (root === null) return null
  if (key > root.val) root.right = deleteNode(root.right, key)
  else if (key < root.val) root.left  = deleteNode(root.left, key)
  else {
    if (root.left === null && root.right === null) root = null
    else if (root.left === null) root = root.right
    else if (root.right === null) root = root.left
    else {
      let p = root.right
      while (p.left) p = p.left
      root.val = p.val
      root.right = deleteNode(root.right, p.val)
    }
  }
  return root
};

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null
  if (key > root.val) root.right = deleteNode(root.right, key)
  else if (key < root.val) root.left = deleteNode(root.left, key)
  else {
    if (root.left  === null &&  root.right === null) root = null
    else if (root.left  === null) root = root.right
    else if (root.right === null) root = root.left
    else {
      let p = root.right
      while (p.left) p = p.left
      root.right = deleteNode(root.right, p.val)
      p.right = root.right
      p.left = root.left
      root = p
    }
  } 
  return root
};

class Solution {
  function deleteNode($root, $key) {
    if ($root === null) return null;
    if ($key > $root->val) $root->right = $this->deleteNode($root->right, $key);
    else if ($key < $root->val) $root->left = $this->deleteNode($root->left, $key);
    else {
      if ($root->left === null && $root->right === null) $root = null;
      else if ($root->left === null) $root = $root->right;
      else if ($root->right === null) $root = $root->left;
      else {
        $p = $root->right;
        while ($p->left !== null) $p = $p->left;
        $root->right = $this->deleteNode($root->right, $p->val);
        $p->left = $root->left;
        $p->right = $root->right;
        $root = $p;
      }
    }
    return $root;
  }
}

class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key > root.val) root.right = deleteNode(root.right, key);
    else if (key < root.val) root.left = deleteNode(root.left, key);
    else {
      if (root.left == null && root.right == null) root = null;
      else if (root.left == null) root = root.right;
      else if (root.right == null) root = root.left;
      else {
        TreeNode p = root.right;
        while (p.left != null) p = p.left;
        root.right = deleteNode(root.right, p.val);
        p.left = root.left;
        p.right = root.right;
        root = p;
      }
    }
    return root;
  }
}

class Solution:
  def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    if root == None: return None
    if key > root.val: root.right = self.deleteNode(root.right, key)
    elif key < root.val: root.left = self.deleteNode(root.left, key)
    elif root.left == None and root.right == None: root = None
    elif root.left == None: root = root.right
    elif root.right == None: root = root.left
    else:
      p = root.right
      while p.left != None: p = p.left
      root.right = self.deleteNode(root.right, p.val)
      p.left = root.left
      p.right = root.right
      root = p
    return root

func deleteNode(root *TreeNode, key int) *TreeNode {
  if root == nil {
    return nil
  }
  if key > root.Val {
    root.Right = deleteNode(root.Right, key)
  } else if key < root.Val {
    root.Left = deleteNode(root.Left, key)
  } else {
    if root.Left == nil && root.Right == nil {
      root = nil
    } else if root.Left == nil {
      root = root.Right
    } else if root.Right == nil {
      root = root.Left
    } else {
      p := root.Right
      for p.Left != nil {
        p = p.Left
      }
      root.Right = deleteNode(root.Right, p.Val)
      p.Left = root.Left
      p.Right = root.Right
      root = p
    }
  }
  return root
}

迭代

var deleteNode = function(root, key) {
  const r = parent = new TreeNode(0, root)
  const setParent = (parent, key, n) => {
    if (parent.left !== null && parent.left.val === key) parent.left = n
    else parent.right = n
  }
  while (root !== null && root.val !== key) {
    parent = root
    if (key > root.val) root = root.right
    else if (key < root.val) root = root.left
  }
  if (root === null) return r.left
  if (root.left === null || root.right === null) setParent(parent, key, root.left || root.right)
  else {
    let p = root.right, pParent = root
    while (p.left) {
      pParent = p
      p = p.left
    }
    setParent(pParent, p.val, p.right)
    p.right = root.right
    p.left = root.left
    setParent(parent, root.val, p)
  }
  return r.left
};

function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  const r: TreeNode = new TreeNode(0, root)
  let parent: TreeNode = r
  const setParent = (parent, key, node) => {
    if (parent.left && parent.left.val === key) parent.left = node
    else parent.right = node
  }
  while (root !== null && root.val !== key) {
    parent = root
    if (key > root.val) root = root.right
    else if (key < root.val) root = root.left
  }
  if (root === null) return r.left
  if (root.left === null || root.right === null) setParent(parent, key, root.left || root.right)
  else {
    let p = root.right, pParent = root
    while (p.left) {
      pParent = p
      p = p.left
    }
    setParent(pParent, p.val, p.right)
    p.right = root.right
    p.left = root.left
    setParent(parent, key, p)
  }
  return r.left
};

class Solution {
  function deleteNode($root, $key) {
    $r = $parent = new TreeNode(0, $root);
    while ($root !== null && $root->val !== $key) {
      $parent = $root;
      if ($key > $root->val) $root = $root->right;
      else if ($key < $root->val) $root = $root->left;
    }
    if ($root === null) return $r->left;
    if ($root->left === null || $root->right === null) $this->setParent($parent, $key, $root->left ?? $root->right);
    else {
      $p = $root->right;
      $pParent = $root;
      while ($p->left !== null) {
        $pParent = $p;
        $p = $p->left;
      }
      $this->setParent($pParent, $p->val, $p->right);
      $p->left = $root->left;
      $p->right = $root->right;
      $this->setParent($parent, $key, $p);
    }
    return $r->left;
  }
  function setParent($parent, $key, $node) {
    if ($parent->left && $parent->left->val === $key) $parent->left = $node;
    else $parent->right = $node;
  }
}

class Solution {
  public TreeNode deleteNode(TreeNode root, int key) {
    TreeNode r = new TreeNode(0, root, root);
    TreeNode parent = r;
    while (root != null && root.val != key) {
      parent = root;
      if (key > root.val) root = root.right;
      else if (key < root.val) root = root.left;
    }
    if (root == null) return r.left;
    if (root.left == null || root.right == null) setParent(parent, key, root.left != null ? root.left : root.right);
    else {
      TreeNode p = root.right;
      TreeNode pParent = root;
      while (p.left != null) {
        pParent = p;
        p = p.left;
      }
      setParent(pParent, p.val, p.right);
      p.left = root.left;
      p.right = root.right;
      setParent(parent, key, p);
    }
    return r.left;
  }
  public void setParent(TreeNode parent, int key, TreeNode node) {
    if (parent.left != null && parent.left.val == key) parent.left = node;
    else parent.right = node;
  }
}

class Solution:
  def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
    r = TreeNode(0, root)
    parent = r
    def setParent(parent, key, node):
      if parent.left and parent.left.val == key: parent.left = node
      else: parent.right = node
    while root != None and root.val != key:
      parent = root
      if key > root.val: root = root.right
      elif key < root.val: root = root.left
    if root == None: return r.left
    if root.left == None or root.right == None: setParent(parent, key, root.left or root.right)
    else:
      p, pParent = root.right, root
      while p.left != None :
        pParent = p
        p = p.left
      setParent(pParent, p.val, p.right)
      p.left = root.left
      p.right = root.right
      setParent(parent, key, p)
    return r.left

func deleteNode(root *TreeNode, key int) *TreeNode {
  r := &TreeNode{0, root, root}
  parent := r 
  for root != nil && root.Val != key {
    parent = root
    if key > root.Val{
      root = root.Right
    } else if key < root.Val {
      root = root.Left
    }
  }
  if root == nil {
    return r.Left
  }
  if root.Left == nil {
    setParent(parent, key, root.Right)
  } else if root.Right == nil {
    setParent(parent, key, root.Left)
  } else {
    p, pParent := root.Right, root
    for p.Left != nil {
      pParent = p
      p = p.Left
    }
    setParent(pParent, p.Val, p.Right)
    p.Left = root.Left
    p.Right = root.Right
    setParent(parent, key, p)
  }
  return r.Left
}
func setParent(parent *TreeNode, key int, node *TreeNode) {
  if parent.Left != nil && parent.Left.Val == key {
    parent.Left = node
  } else {
    parent.Right = node
  }
}

小宇

Github　力扣　 M站　全部原创，请勿转载

递归，迭代 2 种方法后序遍历，求解《1022. 从根到叶的二进制数之和》

递归，迭代（单栈，Java 用 ArrayDeque 实现）2种方法后序遍历，求解《1022. 从根到叶的二进制数之和》

记忆化递归 + 状态压缩掩码：求解《464. 我能赢吗》

记忆化递归，状态压缩掩码，求解《464. 我能赢吗》

递归、迭代：求解《953. 验证外星语词典》

递归、迭代两种方式，求解《953. 验证外星语词典》