[Swift]LeetCode145. 二叉树的后序遍历 | Binary Tree Postorder Traversal
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
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 }