No. 94 - Binary Tree Inorder Traversal
====


---

## [LeetCode 94 -- Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal/)

### 題目描述

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

Example 1.


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

Example 2.


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

---

這裡我會分別講解遞迴 (recursive) 及疊代 (iterative) 的方法。

不過在開始講解解法前，我們先複習一下 tree 的 inorder traversal 的概念是什麼。

Inorder traversal 的概念用一句話解釋就是***先走訪左子樹，再走訪父節點，再走訪右子樹***。從一棵 tree 的 root 開始，只要 root 的左邊還有 node 就代表還有左子樹可以走訪，接著把左邊的 node 當成 root 再看其左邊是否還有子樹，若有則繼續往左走訪直到左邊沒有 node 為止。

當左邊沒有 node 可以走訪後，就會印出當前的 root，接著再走訪右子樹。當走訪到右子樹的 node 後會繼續依照先走訪左子樹... 的順序再走訪一遍。

當當前 root 的左右子樹都走訪過後，代表這個 root 的父節點的左子樹已經走訪完了，就會回到此父節點接著就照著前面所講的走訪完左子樹後的步驟再做一次，依此類推直到走訪完整棵樹的 nodes。

### 解法 1. Recursive Approach

依照上面所講的 inorder traversal 的概念，我們可以很簡單的用 recursive 的方式實現。我們需要一個 `traversal` 的函式來走訪所有的 nodes 以及一個 `res` 的 list 來存 nodes。按照前面的***先走訪左子樹，再走訪父節點，再走訪右子樹*** 的口訣，我們可以很簡單的寫出下面的程式碼:

traversal(node->left, res);  // 先走訪左子樹
res.push_back(node->val);    // 再走訪父節點
traversal(node->right, res); // 再走訪右子樹

完整的 `traversal` 函式會當 `node` 不存在時就會結束

void traversal(TreeNode *node, vector<int> &res) {
  if (node) {
    traversal(node->left, res);
    res.push_back(node->val);
    traversal(node->right, res);
  }
}

最後，完整的程式碼如下:

/**
 * 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 traversal(TreeNode *node, vector<int> &res) {
    if (node) {
      traversal(node->left, res);
      res.push_back(node->val);
      traversal(node->right, res);
    }
  }
  vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    traversal(root, res);
    return res;
  }
};

:::info
這邊 `traversal` 函式的 `res` 使用了 C++ call by reference 的技巧，讓每次的 `res.push()` 都會直接改動到 `inorderTraversal` 函式的 `res` 變數。
:::

### 解法 2. Iterative Approach

只要有了前面的口訣，我們就能很簡單的用 recursive 的方法實現，現在我們要嘗試著使用 iterative 的方法來實現 inorder traversal，完整的程式碼如下:

/**
 * 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> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode *cur;
    
    while (root || !st.empty()) {
      while (root) {           // 走訪左子樹
        st.push(root);         // 紀錄父節點
        root = root->left;
      }
      cur = st.top();          // 回到父節點
      st.pop();
      res.push_back(cur->val); // 走訪父節點
      root = cur->right;       // 走訪右子樹
    }
    return res;
  }
};

Iterative 的方法若要在走訪完左子樹能夠回到父節點再繼續走訪其右子樹，我們需要用一個 stack `st` 來記錄每次走訪左子樹的父節點。

Inorder traversal 一開始會先走訪左子樹且只要左子樹存在就會一直往左邊的 node 走訪直到沒有下一個左邊 node 為止，所以程式碼的 20 - 23 行就是在走訪左子樹並記錄父節點。

當跳出 20 行的 while 迴圈代表前面父節點已經沒有左子樹了，所以我們就要把父節點存到 `res` list 中也就是走訪了父節點，接著走訪此父節點的右子樹。

而第 19 行的最外層 while 迴圈就是在重複著***先走訪左子樹，再走訪父節點，再走訪右子樹*** 的步驟，這個 while 迴圈不是只看當前的 `root` 是否存在，也就是走訪到的 node 存不存在，還要確認紀錄父節點的 stack 也都被清空了才會真的走訪完所有的 nodes。因為如果 stack 還有 node 的話代表還有父節點及其右子樹還沒走訪過。

### 複雜度分析

不論是 recursive 或 iterative 的方法都需要走訪過 tree 的所有 nodes，所以時間複雜度為 $O(N)$

在空間複雜度的分析上，recursive 的方法需要 stack 來存 `traversal` 函式讓之後可以跳回前一個 `traversal` 函式，當 tree 都偏向左或右的時候會有最差的空間複雜度 $O(N)$，而在平均情況下空間複雜度為 $O(\log N)$。

而 iterative 的方法的 stack 會存所有的 nodes 所以空間複雜度為 $O(N)$。

:::info
學會了 inorder traversal，另外還有 preoder traversal 跟 postorder traversal 哦! 請看 [144. Binary Tree Preorder Traversal](https://hackmd.io/@Ji0m0/S1_VMT-L_) 及 [145. Binary Tree Postorder Traversal](https://hackmd.io/@Ji0m0/rybdMTbLO)
:::