[Golang][Leetcode][BinaryTree]刷題系列-144-Preorder Traversal

Contents
144. Binary Tree Preorder Traversal
Level : Easy
原題連結 : Click
題目 :
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
- preorder visit順序 : root -> left -> right
- inorder visit順序 : left -> root -> right
- 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.
|
|
Iterative(Stack)解法
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!