Contents

# 145. Binary Tree Postorder Traversal

## 題目 :

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

### Example :

Note

Example 1:

Input: root = [1,null,2,3] Output: [3,2,1]

Example 2:

Input: root = [] Output: []

Example 3:

Input: root = [1] Output: [1]

Example 4:

Input: root = [1,2] Output: [2,1]

Example 5:

Input: root = [1,null,2] Output: [2,1]

#### 解題思路 :

• 這題需要我們做postorder traversal 作法與preorder類似，可以參考 leetcode144題解

• 但唯一要注意的是在Stack的解法中，我是用reverse result的解法，這樣的解法會看起來更清晰乾淨

• 原本postorder visit 順序是 left -> right -> mid 但由於mid在最後面導致程式碼會較複雜，那若改成 mid -> right -> left，程式碼會簡單許多，因為mid在前面就可以visit到就先把它放進stack，之後會更方便做處理寫法也更像preorder，只是最後須要把結果反轉

### Recursive解法

• time complexity: O(n) , space complexity: O(n)

Runtime: 0 ms, faster than 100.00% of Go online submissions for Binary Tree Postorder Traversal.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 `````` ``````func postorderTraversal(root *TreeNode) []int { var res []int if root == nil { return res } var postorder func(*TreeNode) postorder = func(node *TreeNode) { if node == nil { return } postorder(node.Left) postorder(node.Right) res = append(res, node.Val) } postorder(root) return res } ``````

### Iterative(Stack)解法

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 `````` ``````func postorderTraversal(root *TreeNode) []int { var res []int var stack []*TreeNode if root == nil { return res } stack = append(stack, root) for len(stack) != 0 { visited := stack[len(stack)-1] stack = stack[:len(stack)-1] if visited.Left != nil { stack = append(stack, visited.Left) } if visited.Right != nil { stack = append(stack, visited.Right) } res = append(res, visited.Val) } for i, j:= 0, len(res)-1; i < j; i, j = i+1, j-1 { res[i], res[j] = res[j], res[i] } return res } ``````