[Swift]LeetCode897. 递增顺序查找树 | Increasing Order Search

发布时间：2020-12-14 04:58:24 所属栏目：百科来源：网络整理

导读：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 9O

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:

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 = 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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!