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

链接：450.删除二叉搜索树中的节点
难度：Medium
标签：树、二叉搜索树、二叉树
简介：给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

题解 1 - java

• 编辑时间：2020-02-23
• 内存消耗：41.7MB
• 编程语言：java
• 解法介绍：判断根是否为 null，以及是否为单节点，然后循环获取 key 所在节点，若节点不存在则返回根，若存在则判断节点的度，度为 2 则获取后继节点，删除后继节点，在判断是否为根节点以及在父节点的左右情况。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
		if (root == null)
			return null;
		if (root.left == null && root.right == null) {
			if (root.val == key)
				return null;
			if (root.val != key)
				return root;
		}
		TreeNode node = root;
		TreeNode parent = null;
		while (node!=null&&node.val != key) {
			if (key > node.val) {
				parent = node;
				node = node.right;
			}
			if (key < node.val) {
				parent = node;
				node = node.left;
			}
		}
		if (node == null)
			return root;
		if (node.left != null && node.right != null) {
			TreeNode oldNode = node;
			parent = node;
			node = node.right;
			while (node.left != null) {
				parent = node;
				node = node.left;
			}
			oldNode.val = node.val;
		}
		if (parent == null) {
			if (node.left != null)
				return node.left;
			if (node.right != null)
				return node.right;
		}
		if (node.left == null && node.right == null) {
			if (parent.left == node) {
				parent.left = null;
			} else {
				parent.right = null;
			}
		} else {
			if (parent.left == node) {
				if(node.left!=null)parent.left = node.left;
				else parent.left = node.right;
			} else {
				if(node.left!=null)parent.right = node.left;
				else parent.right = node.right;
			}
		}
		return root;
	}
}

题解 2 - typescript

• 编辑时间：2022-06-02
• 执行用时：24ms
• 内存消耗：31.9MB
• 编程语言：typescript
• 解法介绍：dfs。

class Solution {
   public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        if (root->val > key)
            root->left = deleteNode(root->left, key);
        else if (root->val < key)
            root->right = deleteNode(root->right, key);
        else {
            if (root->left == nullptr || root->right == nullptr) {
                TreeNode* child =
                    root->left == nullptr ? root->right : root->left;
                root = child;
            } else {
                TreeNode* tmp = root->right;
                while (tmp->left) tmp = tmp->left;
                root->val = tmp->val;
                root->right = deleteNode(root->right, tmp->val);
            }
        }
        return root;
    }
};

题解 3 - typescript

• 编辑时间：2021-08-07
• 执行用时：104ms
• 内存消耗：47.3MB
• 编程语言：typescript
• 解法介绍：分别计算度，进行递归删除。

function predecessor(node: TreeNode): TreeNode {
  let ans = node.left!;
  while (ans.right) ans = ans.right;
  return ans;
}
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
  if (root === null) return null;
  if (root.val > key) {
    root.left = deleteNode(root.left, key);
  } else if (root.val < key) {
    root.right = deleteNode(root.right, key);
  } else {
    if (root.left === null || root.right === null) return root.left ?? root.right;
    const p = predecessor(root);
    [p.val, root.val] = [root.val, p.val];
    root.left = deleteNode(root.left, p.val);
  }
  return root;
}