大佬教程收集整理的这篇文章主要介绍了[Swift]LeetCode897. 递增顺序查找树 | Increasing Order Search Tree,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
Given a tree,rearrange the tree in in-order so that the leftmost node in the tree is Now the root of the tree,and every node has no left child and only 1 right child.
Example 1: Input: [5,3,6,2,4,null,8,1,7,9] 5 / 3 6 / \ 2 4 8 / / \ 1 7 9 Output: [1,5,9] 1 2 3 4 5 6 7 8 9
Note:
给定一个树,按中序遍历重新排列树,使树中最左边的结点现在是树的根,并且每个结点没有左子结点,只有一个右子结点。
示例 :
输入:[5,9] 5 / 3 6 / \ 2 4 8 / / \ 1 7 9 输出:[1,9] 1 2 3 4 5 6 7 8 9
提示:
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 increasingBST(_ root: TreeNode?) -> TreeNode? { 16 return increasingBST(root,nil) 17 } 18 19 func increasingBST(_ root:TreeNode?,_ tail:TreeNode?) -> TreeNode? { 20 if root == nil {return tail} 21 var res:TreeNode? = increasingBST(root?.left,root) 22 root?.left = nil 23 root?.right = increasingBST(root?.right,tail) 24 return res 25 } 26 }
88ms
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 increasingBST(_ root: TreeNode?) -> TreeNode? { 16 return increasingBST(root,nil) 17 } 18 19 func increasingBST(_ root: TreeNode?,_ tail: TreeNode?) -> TreeNode? { 20 guard let node = root else { 21 return tail 22 } 23 let left = increasingBST(node.left,nodE) 24 node.left = nil 25 node.right = increasingBST(node.right,tail) 26 return left 27 } 28 }
96ms
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 16 var newParent: TreeNode? 17 var newRoot: TreeNode? 18 19 func increasingBST(_ root: TreeNode?) -> TreeNode? { 20 inorder(root) 21 return newRoot 22 } 23 24 func inorder(_ root: TreeNode?) { 25 guard let root = root else { return } 26 inorder(root.left) 27 if let newParent = newParent { 28 root.left = nil 29 newParent.right = root 30 } else { 31 newRoot = root 32 } 33 newParent = root 34 inorder(root.right) 35 } 36 }
100ms
1 class Solution { 2 var list = [TreeNode?]() 3 func increasingBST(_ root: TreeNode?) -> TreeNode? { 4 inorder(root: root) 5 let node = TreeNode.init(0) 6 list.insert(node,at: 0) 7 for i in 0..<list.count - 1 { 8 list[i]?.left = nil 9 list[i]?.right = list[i+1] 10 } 11 if list.count - 1 > 0 { 12 list[list.count - 1]?.left = nil 13 } 14 return node.right 15 } 16 17 func inorder(root: TreeNode?) { 18 var stack = [TreeNode]() 19 var root = root 20 while root != nil || stack.count > 0 { 21 if root != nil { 22 stack.append(root!) 23 root = root?.left 24 }else { 25 let last = stack.removeLast() 26 list.append(last) 27 root = last.right 28 } 29 } 30 } 31 }
104ms
1 class Solution { 2 var newHead:TreeNode? 3 var nextNode:TreeNode? 4 5 6 func increasingBST(_ root: TreeNode?) -> TreeNode? { 7 8 guard let root = root else 9 { 10 return nil 11 } 12 13 increasingBST(root.left) 14 15 if newHead == nil 16 { 17 newHead = root 18 } 19 root.left = nil 20 if nextNode != nil 21 { 22 nextNode?.right = root 23 } 24 nextNode = root 25 26 increasingBST(root.right) 27 return newHead 28 } 29 }
108ms
1 class Solution { 2 func increasingBST(_ root: TreeNode?) -> TreeNode? { 3 guard let root = root else { 4 return nil 5 } 6 let resultTree = TreeNode(0) 7 var current: TreeNode? = resultTree 8 inorderTraversal(root) { 9 val in 10 current?.right = TreeNode(val) 11 current = current?.right 12 } 13 14 return resultTree.right 15 } 16 } 17 18 19 func inorderTraversal(_ root: TreeNode?,_ visit: (int) -> Void) { 20 guard let root = root else { 21 return 22 } 23 inorderTraversal(root.left,visit) 24 visit(root.val) 25 inorderTraversal(root.right,visit) 26 }
116ms
1 class Solution { 2 func increasingBST(_ root: TreeNode?) -> TreeNode? { 3 var toReturn = getLeft(root) 4 var r = root 5 Helper(r,nil) 6 return toReturn 7 } 8 9 func getLeft(_ root: TreeNode?) -> TreeNode? { 10 var root = root 11 if root == nil { return nil } 12 while root!.left != nil { 13 root = root!.left 14 } 15 return root 16 } 17 18 func Helper(_ root: TreeNode?,_ p: TreeNode?) -> TreeNode? { 19 if root == nil { return p } 20 let prev = Helper(root!.left,p) 21 let r = root!.right 22 root!.left = nil 23 if var prev = prev { 24 prev.right = root 25 } 26 return Helper(r,root) 27 } 28 }
216ms
1 class Solution { 2 func increasingBST(_ root: TreeNode?) -> TreeNode? { 3 var arr = [Int]() 4 midTree(root,&arr) 5 if arr.count == 0 { return nil } 6 else { 7 var root = TreeNode(arr[0]) 8 var temp = root 9 for index in 1..<arr.count { 10 var right = TreeNode(arr[index]) 11 temp.right = right 12 temp = right 13 } 14 return root 15 } 16 } 17 18 func midTree(_ root: TreeNode?,_ arr: inout [Int]) { 19 guard let root = root else { return } 20 if root.left != nil { midTree(root.left,&arr) } 21 arr.append(root.val) 22 if root.right != nil {midTree(root.right,&arr)} 23 } 24 }
以上是大佬教程为你收集整理的[Swift]LeetCode897. 递增顺序查找树 | Increasing Order Search Tree全部内容,希望文章能够帮你解决[Swift]LeetCode897. 递增顺序查找树 | Increasing Order Search Tree所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。