LeetCode0450.DeleteNodeinaBST删除二叉搜索树中的节点【Medium】【Python】【Binarytree】问题LeetCode给定一个根BST和键的节点引用，删除BST中具有给定键的节点。返回BST的根节点引用（可能已更新）。删除基本上可以分为两个阶段：搜索要删除的节点。如果找到该节点，则删除该节点。注意：时间复杂度应为O（高度oftree).Example:root=[5,3,6,2,4,null,7]key=35/\36/\\247给定的要删除的键是3。所以我们找到具有值的节点3并删除它。一个有效的答案是[5,4,6,2,null,null,7]，如以下BST所示。5/\46/\27另一个有效答案是[5,2,6,null,4,null,7]。5/\26\\47个问题根节点root和一个值key，删除二叉搜索树中key对应的节点，保证二叉搜索树的性质不变。返回对二叉搜索树的（可能更新的）根节点的引用。一般来说，删除一个节点可以分为两步：首先找到需要删除的节点；如果找到，请将其删除。说明：要求算法的时间复杂度为O(h)，其中h为树的高度。例子：root=[5,3,6,2,4,null,7]key=35/\36/\\247鉴于要删除的节点的值为3，所以我们先求节点3，并将其删除。正确答案是[5,4,6,2,null,null,7]，如下图所示。5/\46/\27另一个正确答案是[5,2,6,null,4,null,7]。5/\26\\47个思路二叉树Python3代码#定义一个二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=NoneclassSolution:defdeleteNode(self,root:TreeNode,key:int)->TreeNode:#Thetreeisemptyifroot==None:returnNone#找到键并删除它ifroot.val==key:#情况一：两个子节点都为空#情况二：只有一个非空子节点，让这个子节点替换自己ifroot.left==None:returnroot.rightifroot.right==None:returnroot.left#Case3:Yes两个非空子节点，求左子树的最大值，或者右子树的最小值，替换自己#Python3需要一个TreeNode对象minNode=TreeNode(None)minNode=self.getMin(root.right)根。val=minNode.valroot.right=self.deleteNode(root.right,minNode.val)#key在左子树中elifroot.val>key:root.left=self.deleteNode(root.left,key)#key在右子树中elifroot.val
