二叉树删除节点算法详解 - Python 代码示例

二叉树删除节点的算法可以分为以下几步：\n\n1. 首先，需要找到要删除的节点。对于二叉搜索树（Binary Search Tree），可以使用二叉树的查找算法找到要删除的节点；对于普通的二叉树，需要遍历整个树，找到要删除的节点。\n\n2. 找到要删除的节点后，需要考虑三种情况：\n - 如果要删除的节点是叶子节点（没有左右子节点），直接删除即可。\n - 如果要删除的节点只有一个子节点，将子节点接到要删除节点的父节点上，并删除要删除节点。\n - 如果要删除的节点有两个子节点，可以选择以下两种方法：\n - 方法一：找到要删除节点的右子树中的最小节点，将其值替换到要删除节点中，并递归删除右子树中的最小节点。\n - 方法二：找到要删除节点的左子树中的最大节点，将其值替换到要删除节点中，并递归删除左子树中的最大节点。\n\n3. 删除节点后，需要更新二叉树的结构，即将删除节点的父节点的指针指向正确的子节点。\n\n下面是一个示例代码，实现了二叉树删除节点的算法（以二叉搜索树为例）：\n\npython\nclass TreeNode:\n def __init__(self, val):\n self.val = val\n self.left = None\n self.right = None\n\ndef deleteNode(root, key):\n if root is None: # 当前节点为空，返回None\n return None\n\n if key < root.val: # key小于当前节点的值，递归删除左子树中的节点\n root.left = deleteNode(root.left, key)\n elif key > root.val: # key大于当前节点的值，递归删除右子树中的节点\n root.right = deleteNode(root.right, key)\n else: # 当前节点的值等于key，需要删除当前节点\n if root.left is None: # 当前节点只有右子树，将右子树接到当前节点的父节点\n return root.right\n elif root.right is None: # 当前节点只有左子树，将左子树接到当前节点的父节点\n return root.left\n else: # 当前节点既有左子树又有右子树\n # 找到当前节点右子树中的最小节点，并将其值替换到当前节点中\n min_node = findMin(root.right)\n root.val = min_node.val\n # 递归删除右子树中的最小节点\n root.right = deleteNode(root.right, min_node.val)\n\n return root\n\ndef findMin(node):\n while node.left:\n node = node.left\n return node\n\n\n这个算法的时间复杂度为O(logn)（当二叉树为平衡二叉树时），其中n为二叉树的节点数。