-
星空
class Solution(object): def deleteNode(self, root, key): """ :type root: TreeNode :type key: int :rtype: TreeNode """ pre, cur = None, root while cur and cur.val != key: pre = cur if key < cur.val: cur = cur.left elif key > cur.val: cur = cur.right if not cur: return root ncur = cur.right if cur.left: ncur = cur.left self.maxChild(cur.left).right = cur.right if not pre: return ncur if pre.left == cur: pre.left = ncur else: pre.right = ncur return root def maxChild(self, root): while root.right: root = root.right return root
-
星空
public class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null){ return null; } if(key < root.val){ root.left = deleteNode(root.left, key); }else if(key > root.val){ root.right = deleteNode(root.right, key); }else{ if(root.left == null){ return root.right; }else if(root.right == null){ return root.left; } root.val = findMax(root.left).val; root.left = deleteNode(root.left, root.val); } return root; } private TreeNode findMax(TreeNode node){ while(node.right != null){ node = node.right; } return node; } }
-
星空
class Solution { private TreeNode deleteRootNode(TreeNode root) { if (root == null) { return null; } if (root.left == null) { return root.right; } if (root.right == null) { return root.left; } TreeNode next = root.right; TreeNode pre = null; for(; next.left != null; pre = next, next = next.left); next.left = root.left; if(root.right != next) { pre.left = next.right; next.right = root.right; } return next; } public TreeNode deleteNode(TreeNode root, int key) { TreeNode cur = root; TreeNode pre = null; while(cur != null && cur.val != key) { pre = cur; if (key < cur.val) { cur = cur.left; } else if (key > cur.val) { cur = cur.right; } } if (pre == null) { return deleteRootNode(cur); } if (pre.left == cur) { pre.left = deleteRootNode(cur); } else { pre.right = deleteRootNode(cur); } return root; } }
-
星空
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if (!root) return nullptr; if (root->val == key) { if (!root->right) { TreeNode* left = root->left; delete root; return left; } else { TreeNode* right = root->right; while (right->left) right = right->left; swap(root->val, right->val); } } root->left = deleteNode(root->left, key); root->right = deleteNode(root->right, key); return root; } };
-