[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,n

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   9Output: [1,5,9] 1     2         3             4                 5                     6                         7                             8                                 9  

Note:

The number of nodes in the given tree will be between 1 and 100. Each node will have a unique integer value from 0 to 1000.

给定一个树，按中序遍历重新排列树，使树中最左边的结点现在是树的根，并且每个结点没有左子结点，只有一个右子结点。 

示例 ：

输入：[5,9]       5      /     3    6   / \      2   4    8 /        / \ 1        7   9输出：[1,9] 1     2         3             4                 5                     6                         7                             8                                 9   

提示：

给定树中的结点数介于 1 和 100 之间。 每个结点都有一个从 0 到 1000 范围内的唯一整数值。 Runtime: 88 ms Memory Usage: 19.4 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 = nil10  *         self.right = nil11  *     }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 = nil23         root?.right = increasingBST(root?.right,tail)24         return res25     }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 = nil10  *         self.right = nil11  *     }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 tail22         }        23         let left = increasingBST(node.left,node)24         node.left = nil25         node.right = increasingBST(node.right,tail)        26         return left27     }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 = nil10  *         self.right = nil11  *     }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 newRoot22     }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 = nil29             newParent.right = root30         } else {31             newRoot = root32         }        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 = nil13         }14         return node.right15     }16     17     func inorder(root: TreeNode?) {18         var stack = [TreeNode]()19         var root = root20         while root != nil || stack.count > 0 {21             if root != nil {22                 stack.append(root!)23                 root = root?.left24             }else {25                 let last = stack.removeLast()26                 List.append(last)27                 root = last.right28             }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 nil11         }12         13         increasingBST(root.left)14         15         if newhead == nil16         {17             newhead = root18         }19         root.left = nil20         if nextNode != nil21         {22             nextNode?.right = root23         }24         nextNode = root25         26         increasingBST(root.right)27         return newhead28     }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?.right12         }13         14         return resultTree.right15     }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 = root11         if root == nil { return nil }12         while root!.left != nil {13             root = root!.left14         }15         return root16     }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!.right22         root!.left = nil23         if var prev = prev {24             prev.right = root25         }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 = right12                temp = right13            }14            return root15        }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所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。