2023年6月22日发(作者：)

python⼆叉树删除节点_NodeinaBST删除。。。LeetCode 0450. Delete Node in a BST 删除⼆叉搜索树中的节点【Medium】【Python】【⼆叉树】ProblemGiven a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root nodereference (possibly updated) of the lly, the deletion can be divided into two stages:Search for a node to the node is found, delete the : Time complexity should be O(height of tree).Example:root = [5,3,6,2,4,null,7]key = 35/ 3 6/ 2 4 7Given key to delete is 3. So we find the node with value 3 and delete valid answer is [5,4,6,2,null,null,7], shown in the following BST.5/ 4 6/ 2 7Another valid answer is [5,2,6,null,4,null,7].5/ 2 6 4 7问题给定⼀个⼆叉搜索树的根节点 root 和⼀个值 key，删除⼆叉搜索树中的 key 对应的节点，并保证⼆叉搜索树的性质不变。返回⼆叉搜索树(有可能被更新)的根节点的引⽤。⼀般来说，删除节点可分为两个步骤：⾸先找到需要删除的节点；如果找到了，删除它。说明： 要求算法时间复杂度为 O(h)，h 为树的⾼度。⽰例:root = [5,3,6,2,4,null,7]key = 35/ 3 6/ 2 4 7给定需要删除的节点值是 3，所以我们⾸先找到 3 这个节点，然后删除它。⼀个正确的答案是 [5,4,6,2,null,null,7], 如下图所⽰。5/ 4 6/ 2 7另⼀个正确答案是 [5,2,6,null,4,null,7]。5/ 2 6 4 7思路⼆叉树Python3代码# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# = x# = None# = Noneclass Solution:def deleteNode(self, root: TreeNode, key: int) -> TreeNode:# 树为空if root == None:return None# 找到 key，进⾏删除if == key:# 情况 1：两个⼦节点都为空# 情况 2：只有⼀个⾮空⼦节点，让这个孩⼦取代⾃⼰if == None:return f == None:return # 情况 3：有两个⾮空⼦节点，找到左⼦树的最⼤值，或者右⼦树的最⼩值，取代⾃⼰# Python3 需要先有⼀个 TreeNode 对象minNode = TreeNode(None)minNode = () = = Node(, )# key 在左⼦树elif > key: = Node(, key)# key 在右⼦树elif < key: = Node(, key)return rootdef getMin(self, node: TreeNode):# BST 最左边的是最⼩值while != None:node = turn nodeGitHub链接