[Swift]LeetCode897. 递增顺序查找树 | Increasing Order Search Tree
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10606692.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,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,3,6,2,4,null,8,1,null,null,null,7,9]
5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9
输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,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 }