孩子兄弟二叉树删除结点
时间: 2023-06-10 07:07:34 浏览: 108
统计二叉树中叶子结点的个数-数据结构第六章
二叉树删除节点有以下几种情况:
1. 被删除的节点是叶子节点,直接删除即可。
2. 被删除的节点只有一个子节点,将该子节点替换被删除的节点即可。
3. 被删除的节点有两个子节点,需要找到被删除节点的中序遍历的后继节点(即比被删除节点大的最小节点),将后继节点的值复制到被删除节点中,然后将后继节点删除。
下面是一个示例代码,实现了二叉树删除节点的功能:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root: TreeNode, key: int) -> TreeNode:
if not root:
return None
if root.val == key:
# 被删除的节点是叶子节点或只有一个子节点
if not root.left:
return root.right
if not root.right:
return root.left
# 被删除的节点有两个子节点,找到后继节点
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
# 删除后继节点
root.right = deleteNode(root.right, successor.val)
elif root.val > key:
root.left = deleteNode(root.left, key)
else:
root.right = deleteNode(root.right, key)
return root
```
该代码中,函数 `deleteNode` 接受一个二叉树的根节点和一个需要被删除的值,返回删除节点后的二叉树的根节点。如果根节点为空,直接返回 `None`。如果根节点的值等于删除值,根据情况进行删除操作。如果根节点的值大于删除值,递归处理左子树;否则递归处理右子树。最后返回删除节点后的根节点。
阅读全文