从二叉树中删除节点的操作可以分为三种情况:
以下是一个示例的Python代码实现:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def deleteNode(root, key):
if not root:
return root
if key < root.val:
root.left = deleteNode(root.left, key)
elif key > root.val:
root.right = deleteNode(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
min_node = findMin(root.right)
root.val = min_node.val
root.right = deleteNode(root.right, min_node.val)
return root
def findMin(node):
while node.left:
node = node.left
return node
这段代码实现了从二叉树中删除指定节点的功能。其中,deleteNode
函数用于递归地删除节点,findMin
函数用于找到右子树中的最小节点。
这个算法的时间复杂度为O(logN),其中N为二叉树中节点的总数。在删除节点时,需要遍历二叉树找到要删除的节点,最坏情况下需要遍历整个二叉树,因此时间复杂度为O(logN)。
TVP分享会
云+社区技术沙龙[第14期]
原引擎 | 场景实战系列
云+社区技术沙龙[第6期]
腾讯云GAME-TECH沙龙
serverless days
云+社区开发者大会(北京站)
云+社区技术沙龙[第12期]
云+社区技术沙龙[第21期]
领取专属 10元无门槛券
手把手带您无忧上云