Contents

# 144. Binary Tree Preorder Traversal

## 題目 :

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

### Example :

Note

Example 1:

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

Example 2:

Input: root = [] Output: []

Example 3:

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

Example 4:

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

Example 5:

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

#### 解題思路 :

• 這題需要我們做preorder traversal
• 類似的題目還有inorder & postorder
• 若要分辨之間的差異需要先將binary tree的定義釐清，binary tree是由一個root node 加上 left child tree(左子樹) 加上 right child tree(右子樹)組成
• 所以根據visit的順序可以分成preorder , inorder , postorder
1. preorder visit順序 : root -> left -> right
2. inorder visit順序 : left -> root -> right
3. postorder順序 : left -> right -> root

• 所以在這題實現preorder traversal我們須先將visit root 再 visit 左子樹 再 visit 右子樹
• 做binary tree traversal可以用recursive or Iterative(Stack)

### Recursive解法

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

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

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````func preorderTraversal(root *TreeNode) []int { res := make([]int,0) var preorder func(node *TreeNode) preorder = func(node *TreeNode) { if node == nil { return } res = append(res, node.Val) preorder(node.Left) preorder(node.Right) } preorder(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 `````` ``````func preorderTraversal(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] res = append(res,visited.Val) if visited.Right != nil { stack = append(stack, visited.Right) } if visited.Left != nil { stack = append(stack, visited.Left) } } return res } ``````