[Swift]LeetCode114.二叉树展开为链表|FlattenBinaryTreetoLinkedList

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

The flattened tree should look like:

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

将其展开为：

20ms

 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 flatten(_ root: TreeNode?) {
16         guard let root = root else { return }
17         var l = root.left != nil;
18         var r = root.right != nil;
19         flatten(root.left)
20         flatten(root.right)
21         if (l && r) {
22             var left = root.left!;
23             let right = root.right;
24             root.right = left;
25             root.left = nil;
26             while (left.right != nil) {
27                 left = left.right!;
28             }
29             left.right = right;
30         } else if (l) {
31             root.right = root.left;
32             root.left = nil;
33         }
34     }
35 }

20ms

 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 flatten(_ root: TreeNode?) {
16         if root == nil {
17             return
18         } else {
19             flatten(root!.left)
20             flatten(root!.right)
21             if var node = root!.left {
22                 while node.right != nil {
23                     node.left = nil
24                     node = node.right!
25                 }
26                 node.right = root!.right
27                 root!.right = root!.left
28                 root!.left = nil
29             }
30         }
31     }
32 }

24ms

 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     var pre : TreeNode?
16     func flatten(_ root: TreeNode?) {
17         if root == nil{
18             return
19         }
20         flatten(root?.right)
21         flatten(root?.left)
22         root?.right = pre
23         root?.left = nil
24         pre = root
25     }
26 }

28ms

 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 flatten(_ root: TreeNode?) {
16         helper(root)
17     }
18     
19     private func helper(_ node: TreeNode?) -> TreeNode? {
20         var node = node
21         if node == nil {
22             return node
23         }
24         if node!.left == nil && node!.right == nil {
25             return node
26         }
27         
28         let left = node!.left, right = node!.right
29         node!.left = nil
30         
31         if let left = left {
32             node!.right = left
33             node = helper(left)
34         }
35         if let right = right {
36             node!.right = right
37             node = helper(right)
38         }
39         
40         return node
41     }
42 }

40ms

 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     var array = [Int]()
16     func flatten(_ root: TreeNode?) {
17         if(root == nil){ return }
18         traverse(root)
19         root!.left = nil
20         root!.right = nil
21         var currentNode = root
22         for index in 1 ..< array.count{
23             currentNode!.right = TreeNode(array[index])
24             currentNode = currentNode!.right
25         }
26     }
27     func traverse(_ root: TreeNode?){
28         if(root == nil){ return }
29         self.array.append(root!.val)
30         traverse(root!.left)
31         traverse(root!.right)
32     }
33 }