Article From:https://www.cnblogs.com/strengthen/p/9968229.html

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?

Given a binary tree, return itsPost orderTraversal.

Example:

`Input: [1, null, 2, 3]One"Two/ThreeOutput: [3,2,1]`

Advanced: Recursive algorithm is very simple. Can you complete it by iterative algorithm?

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 }```