• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode144. 二叉树的前序遍历 | Binary Tree Preorder Traversal

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

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

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given a binary tree, return the preorder traversal of its nodes\' values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

Follow up: Recursive solution is trivial, could you do it iteratively?


给定一个二叉树,返回它的 前序 遍历。

 示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?


8ms

 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 
15 class Solution {
16     
17     func preorderTraversal(_ root: TreeNode?) -> [Int] {
18         guard let root = root else { return [] }
19         var stack = [root]
20         var processed = [Int]()
21         
22         while let node = stack.popLast() {
23             processed.append(node.val)
24             
25             if let right = node.right {
26                 stack.append(right)
27             }
28             
29             if let left = node.left {
30                 stack.append(left)
31             }
32         }
33         
34         return processed
35     }
36     
37 }

8ms

 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 preorderTraversal(_ root: TreeNode?) -> [Int] {
16         if (root == nil) {
17             return Array()
18         }
19         
20         var res : [Int] = [Int]()
21         var stack : [TreeNode] = [TreeNode]()
22         stack.append(root!)
23         while(stack.count > 0) {
24             let node : TreeNode = stack.last!
25             stack.removeLast()
26             if (node.right != nil) {
27                 stack.append(node.right!)
28             }
29             if (node.left != nil) {
30                 stack.append(node.left!)
31             }
32             res.append(node.val)
33         }
34         
35         return res
36     }
37 }

12ms

 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 preorderTraversal(_ root: TreeNode?) -> [Int] {
16         var res = [Int]()
17         var stack = [TreeNode]()
18         var node = root
19         while(stack.count > 0 || node != nil) {
20             if node != nil {
21                 stack.append(node!)
22                 res.append(node!.val)
23                 node = node!.left
24             }
25             else {
26                 node = stack.removeLast().right
27             }
28         }
29         return res
30     }
31 }

16ms

 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 result = [Int]()
16     
17     func preorderTraversal(_ root: TreeNode?) -> [Int] {
18         guard let root = root else {
19             return result
20         }
21         result.append(root.val)
22         preorderTraversal (root.left)    
23         preorderTraversal (root.right)    
24          
25         return result
26     }
27 }

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 preorderTraversal(_ root: TreeNode?) -> [Int] {
16         guard let root = root else { return [] }
17         var result = [Int]()
18         var stack: Stack<TreeNode> = [root]
19         
20         while !stack.isEmpty {
21             let node = stack.pop()
22             result.append(node.val)
23             
24             if let right = node.right {
25                 stack.push(right)
26             }
27             if let left = node.left {
28                 stack.push(left)
29             }
30         }
31         
32         return result
33     }
34 }
35 
36 public struct Stack<T> {
37     private var items: [T]
38 
39     public init() {
40         items = []
41     }
42 
43     public mutating func push(_ value: T) {
44         items.append(value)
45     }
46 
47     public mutating func pop() -> T {
48         return items.removeLast()
49     }
50 
51     public func peek() -> T? {
52         return items.last
53     }
54 
55     public var isEmpty: Bool {
56         return items.isEmpty
57     }
58 }
59 
60 extension Stack: ExpressibleByArrayLiteral {
61     public init(arrayLiteral elements: T...) {
62         items = elements
63     }
64 }

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 preorderTraversal(_ root: TreeNode?) -> [Int] {
16         var res: [Int] = []
17         if let rootval = root?.val{
18             res.append(rootval)
19         }
20         if root?.left != nil{
21             let left = preorderTraversal(root?.left)
22             res.append(contentsOf: left)
23         }
24         if root?.right != nil{
25             let right = preorderTraversal(root?.right)
26             res.append(contentsOf: right)
27         }
28         return res
29     }
30 }

 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 preorderTraversal(_ root: TreeNode?) -> [Int] {
16         guard let root = root else {
17             return []
18         }
19         
20         var result = [Int]()
21         var stack = Stack<TreeNode>()
22         stack.push(root)
23 
24         while !stack.isEmpty {
25             let node = stack.pop()
26             result.append(node.val)
27             
28             if let right = node.right {
29                 stack.push(right)
30             }
31             if let left = node.left {
32                 stack.push(left)
33             }
34         }
35         
36         return result
37     }
38     
39     public struct Stack<T>: ExpressibleByArrayLiteral {
40         private var items: [T]
41 
42         public init() {
43             items = []
44         }
45         
46         public init(arrayLiteral: T...) {
47             self.init()
48             for element in arrayLiteral {
49                 self.push(element)
50             }
51         }
52 
53         public mutating func push(_ value: T) {
54             items.append(value)
55         }
56 
57         public mutating func pop() -> T {
58             return items.removeLast()
59         }
60 
61         public func peek() -> T? {
62             return items.last
63         }
64 
65         public var isEmpty: Bool {
66             return items.isEmpty
67         }
68     }
69 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift学习笔记之-泛型发布时间:2022-07-13
下一篇:
[Swift A] - DataSource 与 Delegate有啥区别?发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap