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

[Swift]LeetCode145.二叉树的后序遍历|BinaryTreePostorderTraversal

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

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

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

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

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

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

Example:

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

Output: [3,2,1]

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


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

示例:

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

输出: [3,2,1]

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


 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 struct NodeId {
16     let node: TreeNode 
17     let id: Int 
18 }
19 
20 class Solution {
21 
22     func postorderTraversal(_ root: TreeNode?) -> [Int] {
23         var node = root 
24         var stack = [TreeNode]()
25         var res = [Int]()
26         
27         while stack.count > 0 || node != nil {
28             if node != nil {
29                 res.insert(node!.val, at: 0)
30                 stack.append(node!)
31                 node = node!.right 
32                 
33             } else {
34                 node = stack.removeLast().left 
35             }
36         }
37         
38         return res 
39     }
40 }

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

 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 postorderTraversal(_ root: TreeNode?) -> [Int] {
16         guard let node = root else { return [] }
17         
18         var results = [Int]()
19         traverse(node, &results)
20         return results
21     }
22     
23     func traverse(_ root: TreeNode?, _ results: inout [Int]) {
24         guard let node = root else { return }
25         
26         traverse(node.left, &results)
27         traverse(node.right, &results)
28         results.append(node.val)
29     }
30 }

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     func postorderTraversal(_ root: TreeNode?) -> [Int] {
16         guard let root = root else {
17             return []
18         }
19         
20         var result = [Int]()
21         var stack = [root]
22         
23         while !stack.isEmpty {
24             let node = stack.removeLast()
25             result.append(node.val)
26             if let leftNode = node.left {
27                 stack.append(leftNode)
28             }
29             if let rightNode = node.right {
30                 stack.append(rightNode)
31             }
32         }
33         
34         return result.reversed()
35     }
36     
37     func postorderTraversal_Rec(_ root: TreeNode?) -> [Int] {
38         var result = [Int]()
39         
40         postorder(root, &result)
41         
42         return result
43     }
44     
45     private func postorder(_ root: TreeNode?, _ result: inout [Int]) {
46         guard let root = root else {
47             return
48         }
49         
50         postorder(root.left, &result)
51         postorder(root.right, &result)
52         result.append(root.val)
53     }
54 }

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     var arr = [Int]()
16     func postorderTraversal(_ root: TreeNode?) -> [Int] {
17         if let r = root {
18             postorderTraversal(r.left)
19             postorderTraversal(r.right)
20             arr.append(r.val)
21             return arr
22         }
23         else {
24             return arr
25         }
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 postorderTraversal(_ root: TreeNode?) -> [Int] {
16         guard (root != nil) else {
17             return []
18         }
19         var result = [Int]()
20         result += self.postorderTraversal(root?.left)
21         result += self.postorderTraversal(root?.right)
22         result.append((root?.val)!)
23         return result
24     }
25 }

32ms

 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 postorderTraversal(_ root: TreeNode?) -> [Int] {
16         class Node {
17             let elem: TreeNode?
18             var n: Int
19             init(elem: TreeNode?, n: Int = 0) {
20               self.elem = elem
21               self.n = n
22             }
23         }
24         var result: [TreeNode] = []
25         var stack: [Node] = []
26         var node: Node = Node(elem: root, n: 0)
27         while node.elem != nil || !stack.isEmpty {
28             if node.elem != nil {
29               node.n = node.n + 1
30               stack.append(node)
31               node = Node(elem: node.elem!.left, n: 0)
32             } else {
33               node = stack.last!
34               node.n = node.n + 1
35               if node.n == 3 {
36                 node = stack.removeLast()
37                 result.append(node.elem!)
38                 node = Node(elem: nil, n: 0)
39               } else {
40                 node = Node(elem: node.elem!.right, n: 0)
41               }
42             }
43         }
44         let ans = result.map {
45             $0.val
46         }
47         return ans
48     }
49 }

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[ios][swift]提示框,并自动消失发布时间:2022-07-13
下一篇:
[Swift]LeetCode1040.移动石子直到连续II|MovingStonesUntilConsecutiveII发布时间: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