在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly Given such a binary tree, you need to output the second minimum value in the set made of all the nodes' value in the whole tree. If no such second minimum value exists, output -1 instead. Example 1: Input: 2 / \ 2 5 / \ 5 7 Output: 5 Explanation: The smallest value is 2, the second smallest value is 5. Example 2: Input: 2 / \ 2 2 Output: -1 Explanation: The smallest value is 2, but there isn't any second smallest value. 给定一个非空特殊的二叉树,每个节点都是正数,并且每个节点的子节点数量只能为 给出这样的一个二叉树,你需要输出所有节点中的第二小的值。如果第二小的值不存在的话,输出 -1 。 示例 1: 输入: 2 / \ 2 5 / \ 5 7 输出: 5 说明: 最小的值是 2 ,第二小的值是 5 。 示例 2: 输入: 2 / \ 2 2 输出: -1 说明: 最小的值是 2, 但是不存在第二小的值。 4ms 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 findSecondMinimumValue(_ root: TreeNode?) -> Int { 16 guard let root = root else{ 17 return -1 18 } 19 var q = [TreeNode]() 20 var set = Set<Int>() 21 q.append(root) 22 while(q.count>0){ 23 for _ in q{ 24 var d = q.removeFirst() 25 if(d.val != root.val){ 26 set.insert(d.val) 27 } 28 29 if let r = d.right{ 30 q.append(r) 31 } 32 if let l = d.left{ 33 q.append(l) 34 } 35 } 36 37 } 38 var min = Int.max 39 for item in set{ 40 if(item < min ){ 41 min = item 42 } 43 } 44 return min == Int.max ? -1 : min 45 } 46 } 8ms 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 findSecondMinimumValue(_ root: TreeNode?) -> Int { 16 guard let root = root else { 17 return -1 18 } 19 20 var firstMin: Int = Int.max 21 var secondMin: Int = firstMin 22 inorderTraversal(root) { 23 value in 24 firstMin = min(firstMin, value) 25 } 26 27 inorderTraversal(root) { 28 value in 29 if value != firstMin { 30 secondMin = min(secondMin, value) 31 } 32 } 33 return secondMin == Int.max ? -1 : secondMin 34 } 35 } 36 37 func inorderTraversal(_ root: TreeNode?, _ visit: (Int) -> Void) { 38 guard let root = root else { 39 return 40 } 41 42 inorderTraversal(root.left, visit) 43 visit(root.val) 44 inorderTraversal(root.right, visit) 45 } Runtime: 12 ms
Memory Usage: 18.9 MB
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 findSecondMinimumValue(_ root: TreeNode?) -> Int { 16 return helper(root, root!.val) 17 } 18 19 func helper(_ node: TreeNode?,_ first:Int) -> Int 20 { 21 if node == nil {return -1} 22 if node!.val != first {return node!.val} 23 var left:Int = helper(node?.left, first) 24 var right:Int = helper(node?.right, first) 25 return (left == -1 || right == -1) ? max(left, right) : min(left, right) 26 } 27 } 24ms 1 class Solution { 2 func findSecondMinimumValue(_ root: TreeNode?) -> Int 3 { 4 guard let root = root else { return -1 } 5 var first = root.val 6 var second = Int.max 7 recursion(root, &first, &second) 8 recursion(root, &second, &first) 9 return second == Int.max ? -1 : second 10 } 11 12 func recursion(_ root: TreeNode?, _ first: inout Int, _ second: inout Int) 13 { 14 guard let root = root else { return } 15 if first > root.val && root.val != second 16 { 17 first = root.val 18 } 19 recursion(root.left, &first, &second) 20 recursion(root.right, &first, &second) 21 } 22 }
|
请发表评论