No. 144 - Binary Tree Preorder Traversal
====
---
## [LeetCode 144 -- Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)
### 題目描述
Given the root of a binary tree, return the preorder traversal of its nodes' values.
Example 1.
```
Input: root = [1,null,2,3]
Output: [1,2,3]
```
Example 2.
```
Input: root = [1,2]
Output: [1,2]
```
---
這裡我會分別講解遞迴 (recursive) 及疊代 (iterative) 的方法。
這題與 [94. Binary Tree Inorder Traversal](https://hackmd.io/QhRYCHmJQdu8NJb-lDVv-g) 概念類似，可以先看完 inorder traversal 的解法便能較快的理解 preorder traversal。
### 解法 1. Recursive Approach
Preorder traversal 就是***先走訪父節點，再走訪左子樹，再走訪右子樹***。
我們可以直接把上面的觀念寫成下面的程式碼:
```cpp=
res.push_back(node->val); // 先走訪父節點
traversal(node->left, res); // 再走訪左子樹
traversal(node->right, res); // 再走訪右子樹
```
而 `traversal` 函式的作法如下所示，只有當走訪的 node 存在的時候才會繼續做 preorder traversal。
```cpp=
void traversal(TreeNode *node, vector<int> &res) {
if (node) {
res.push_back(node->val);
traversal(node->left, res);
traversal(node->right, res);
}
}
```
有了 `traversal` 函式我們就可以直接呼叫這個函式完成我們的 preorder traversal。
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void traverse(TreeNode *node, vector<int> &res) {
if (!node)
return;
res.push_back(node->val);
traverse(node->left, res);
traverse(node->right, res);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
traverse(root, res);
return res;
}
};
```
### 解法 2. Iterative Approach 1
接著我們要用 iterative 的方法來做出 preorder traversal，其作法如下:
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root)
return res;
stack<TreeNode*> st;
st.push(root);
while (!st.empty()) {
root = st.top();
res.push_back(root->val);
st.pop();
if (root->right)
st.push(root->right);
if (root->left)
st.push(root->left);
}
return res;
}
};
```
我們會需要一個 stack 來記錄每個走訪的 node，首先我們先將 root 丟進這個 stack。接著我們只要看這個 stack 裡面還有沒有 node，只要有就要把它 pop 出來存到 `res` 的 list，並且每一次 pop 就會把該 node 的左邊 node 跟右邊 node 丟到 stack 中，其順序是先丟右邊 node 再丟左邊 node，因為我們是會先走訪左子樹再走訪右子樹。
這樣一來每 pop 出一個 node 就是先走訪了父節點，接著就會再丟兩個 node 進入 stack，所以下一次的 pop 就代表先走訪左子樹的父節點，若左子樹不存在就會是走訪右子樹的父節點，這也就是 preorder traversal ***先走訪父節點，再走訪左子樹，再走訪右子樹*** 的作法。
### 解法 3. Iterative Approach 2
Iterative 還有另一種作法，我們不用把每個左右邊 node 都存進 stack 中，只要把右邊 node 存進 stack 裡就好，而每次走訪左邊 node 時就會直接將其存到 `res` 的 list。
完整程式碼如下所示:
```cpp=
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root)
return res;
stack<TreeNode*> st;
while (!st.empty() || root) {
while (root) {
res.push_back(root->val);
if (root->right)
st.push(root->right);
root = root->left;
}
if (!st.empty()) {
root = st.top();
st.pop();
}
}
return res;
}
};
```
程式碼的第 20 - 25 行，會一直走訪左邊 node 直到左邊 node 不存在為止，每一次的走訪就會把 node 存到 `res` 代表走訪父節點，再走訪左子樹，並同時把右邊 node 放到 stack，當左邊 node 走訪完之後，就會改走訪右邊 node，第 26 - 28 行就會把右邊 node pop 出來之後再繼續走訪父節點，再走訪左子樹的步驟。
### 複雜度分析
時間複雜度分析上，不論是 recursive 還是 iterative 的作法都是要走訪所有的 nodes，所以時間複雜度為 $O(N)$。
空間複雜度分析上，recursive 的方法需要 stack 來存 `traversal` 函式讓之後可以跳回前一個 `traversal` 函式，當 tree 都偏向左或右的時候會有最差的空間複雜度 $O(N)$。因為若所有的 nodes 都是在左邊的話，則每次進入 `traversal` 函式遇到 `traversal(node->left)` 就會把當前 `traversal` 函式存入 stack 在繼續呼叫下一個 `traversal`。而正因為全部 nodes 都在左邊，stack 會存所有 nodes 數的 `traversal` 函式，中途不會被 pop 掉。
若不是在這種全部偏左或右的極端情況下，平均情況下空間複雜度為 $O(\log N)$。
而 iterative 的作法空間複雜度都只需要 $O(H)$，$H$ 為 tree 的高。
為什麼呢?
第一個 iterative 的作法，每一次從 stack pop node 就會最多在 push 兩個 node。在第一層 root 的時候 stack 只會存 root 所以只有一個，root pop 出來後會把它的左右 nodes 都 push 進 stack，stack 內就會存 2 個 nodes，而這也代表這個 tree 高有兩層。當我們在 pop 左邊的 node 時會再把它的下一層的左右 nodes push 進 stack 而這時 stack 有 3 個 nodes，tree 高也有三層。
第二個 iterative 的作法，stack 只會在每次走訪左邊 node 時存右邊 node，所以只要能夠一直往左邊走訪就會需要一直存右邊 node，而要存的右邊 node 數量就是看左邊走訪能到多深，這也就是 tree 的高。
:::info
學會了 preoder traversal，另外還有 inorder traversal 跟 postorder traversal 哦! 請看 [94. Binary Tree Inorder Traversal](https://hackmd.io/@Ji0m0/HyAgG6bU_) 及 [145. Binary Tree Postorder Traversal](https://hackmd.io/@Ji0m0/rybdMTbLO)
:::
Sign in with Wallet
Connect another wallet