在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divided into two stages:
Note: Time complexity should be O(height of tree). Example: root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \ 2 7 Another 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 = 3 5 / \ 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 152ms 1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? { 16 /* 17 * 思路: 18 * 1,找到需要被删除的节点 19 * 2,没有子节点,直接删除 20 * 3,一个子节点,直接替换 21 * 4,两个子节点,中序遍历的第一个节点替换,BST的中序遍历就是排好序的 22 */ 23 if root == nil {return root} 24 var temp = root 25 // 在左子树中寻找删除 26 if temp!.val > key{ 27 28 temp?.left = deleteNode(temp?.left, key) 29 }else if temp!.val < key{ 30 // 在右子树中删除 31 temp?.right = deleteNode(temp?.right, key) 32 }else{ 33 // 找到了需要删除的节点,如果节点有一个子节点 34 if temp?.left == nil || temp?.right == nil{ 35 temp = temp?.left == nil ? temp?.right : temp?.left 36 }else{ 37 var node = temp!.right! 38 while node.left != nil{ 39 node = node.left! 40 } 41 temp!.val = node.val 42 temp?.right = deleteNode(temp?.right, node.val) 43 } 44 } 45 return temp 46 } 47 } 164ms 1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? { 16 guard let root = root else { 17 return nil 18 } 19 20 if key < root.val { 21 root.left = deleteNode(root.left, key) 22 } else if key > root.val { 23 root.right = deleteNode(root.right, key) 24 } else { 25 if root.left == nil { 26 return root.right 27 } else if root.right == nil { 28 return root.left 29 } else { 30 let minNode = findMin(root.right!) 31 root.val = minNode.val 32 root.right = deleteNode(root.right, root.val) 33 } 34 } 35 36 return root 37 } 38 39 func findMin(_ root: TreeNode) -> TreeNode { 40 var root = root 41 42 while let leftNode = root.left { 43 root = leftNode 44 } 45 46 return root 47 } 48 } 184ms 1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * public var val: Int 5 * public var left: TreeNode? 6 * public var right: TreeNode? 7 * public init(_ val: Int) { 8 * self.val = val 9 * self.left = nil 10 * self.right = nil 11 * } 12 * } 13 */ 14 class Solution { 15 func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? { 16 var root = root 17 if root == nil {return nil} 18 if root!.val == key 19 { 20 if root!.right == nil {return root!.left} 21 else 22 { 23 var cur:TreeNode? = root!.right 24 while(cur?.left != nil) 25 { 26 cur = cur!.left 27 } 28 (root!.val,cur!.val) = (cur!.val,root!.val) 29 } 30 } 31 root!.left = deleteNode(root!.left, key) 32 root!.right = deleteNode(root!.right, key) 33 return root 34 } 35 }
|
请发表评论